汽车网站设计模板,邯郸市建设局网站,wordpress如何让主题支持子主题,网站检测报告哪里做描述 BZOJ: http://www.lydsy.com/JudgeOnline/problem.php?id1798 Codevs: http://codevs.cn/problem/2216/ 给出n和行星的质量,进行m次操作: 1.将[l,r]区间内所有行星质量*c. 2.将[l,r]区间内所有行星质量c. 3.询问[l,r]区间内行星质量和. 分析 双标记线段树,多加一个乘法的…描述 BZOJ: http://www.lydsy.com/JudgeOnline/problem.php?id1798 Codevs: http://codevs.cn/problem/2216/ 给出n和行星的质量,进行m次操作: 1.将[l,r]区间内所有行星质量*c. 2.将[l,r]区间内所有行星质量c. 3.询问[l,r]区间内行星质量和. 分析 双标记线段树,多加一个乘法的标记.a[k]位置的标记表示的是要传给a[k]的子节点的值,乘法位置为a[k].f,加法为a[k].p,表示的是先乘后加.按照先乘后加的规定,当跟新值时,axb变为(axb)*c1c2axc1bc1c2(axc1)(bc1c2),也就是标记向下传递(push_down)的时候,乘法位置要乘,加法位置要先乘后加. 之前一直wa,最后才发现数组没开够... 感觉好像把乘法转化为加法也能做...但没尝试. 注意: 1.最好在确保扔给函数的参数都是取过模的,这样不容易出错. 2.可以不用long long定义,在乘法的时候强制转换一下就好了. 1 #includecstdio2 #includealgorithm3 #define ll long long4 #define lson 2*k5 #define rson 2*k16 7 const int maxn1e55;8 int n,m,mod;9 int w[maxn];10 struct node { int l,r,x,f,p; }a[3*maxn];11 12 void build_tree(int l,int r,int k)13 {14 a[k].ll; a[k].rr; a[k].f1; a[k].p0;15 if(lr)16 {17 a[k].xw[l]; 18 return; 19 } 20 int midl(r-l)/2;21 build_tree(l,mid,lson);22 build_tree(mid1,r,rson);23 a[k].x(a[lson].xa[rson].x)%mod;24 }25 26 inline void cal(int k,int f,int p)27 {28 a[k].x(int)((((ll)a[k].x*(ll)f)%mod((ll)(a[k].r-a[k].l1)%mod)*(ll)p)%mod);29 a[k].f(int)(((ll)a[k].f*(ll)f)%mod);30 a[k].p(int)((((ll)a[k].p*(ll)f)%modp)%mod);31 }32 33 inline void push_down(int k)34 {35 cal(lson,a[k].f,a[k].p);36 cal(rson,a[k].f,a[k].p);37 a[k].f1;38 a[k].p0;39 }40 41 void update(int l,int r,int k,int f,int p)42 {43 if(a[k].lla[k].rr)44 {45 cal(k,f,p);46 return;47 }48 if(a[k].f!1||a[k].p)49 {50 push_down(k);51 }52 int mida[k].l(a[k].r-a[k].l)/2;53 if(rmid)54 {55 update(l,r,lson,f,p);56 }57 else if(lmid)58 {59 update(l,r,rson,f,p);60 }61 else62 {63 update(l,mid,lson,f,p);64 update(mid1,r,rson,f,p);65 }66 a[k].x(a[lson].xa[rson].x)%mod;67 }68 69 int search(int l,int r,int k)70 {71 if(a[k].lla[k].rr)72 {73 return a[k].x;74 }75 if(a[k].f!1||a[k].p)76 {77 push_down(k);78 }79 int mida[k].l(a[k].r-a[k].l)/2;80 if(rmid)81 {82 return (search(l,r,lson)%mod);83 }84 else if(lmid)85 {86 return (search(l,r,rson)%mod);87 }88 else89 {90 return ((search(l,mid,lson)search(mid1,r,rson))%mod);91 }92 }93 94 int main()95 {96 #ifndef ONLINE_JUDGE97 freopen(star.in,r,stdin);98 freopen(star.out,w,stdout);99 #endif
100 scanf(%d%d,n,mod);
101
102 for(int i1;in;i)
103 {
104 scanf(%d,w[i]);
105 }
106 build_tree(1,n,1);
107 scanf(%d,m);
108 int qry,l,r,c;
109 for(int i1;im;i)
110 {
111 scanf(%d%d%d,qry,l,r);
112 switch(qry)
113 {
114 case 1:
115 scanf(%d,c);
116 c%mod;
117 update(l,r,1,c,0);
118 break;
119 case 2:
120 scanf(%d,c);
121 c%mod;
122 update(l,r,1,1,c);
123 break;
124 case 3:
125 printf(%d\n,search(l,r,1));
126 break;
127 }
128 }
129 #ifndef ONLINE_JUDGE
130 fclose(stdin);
131 fclose(stdout);
132 system(star.out);
133 #endif
134 return 0;
135 } View Code 转载于:https://www.cnblogs.com/Sunnie69/p/5436371.html
