今天集训队打比赛的一道题，很明显是个线段树，，我们队照着lrj蓝书敲了一通，机智的将修改值和加和改成了位运算：|=
但是好像哪里出了点小问题，就是不对，赛后又水了一遍，竟然过了。。。发现还是lrj的书好啊，市面上的模板一点也不好用，连区间修改都没有 。
等集训完了要静心好好系统的学习一下线段树 。 多看多刷lrj的书 。
细节参见代码：
#include<bits/stdc++.h>using namespace std;const int maxn = 1000000 + 5;int n,m,_sum,v,a,b,y11,y22,c,setv[maxn * 3],sumv[maxn * 3];char cmd[5];void pushdown(int o) {int lc = o*2 , rc = o*2 + 1;if(setv[o] >= 0) {setv[lc] = setv[rc] = setv[o] ;setv[o] = -1;}}void maintain(int o,int L,int R) {int lc = o*2 , rc = o*2 + 1;sumv[o] = 0;if(R > L) {sumv[o] = sumv[lc] | sumv[rc];}if(setv[o] >= 0) { sumv[o] = setv[o]; return ; }return ;}void update(int o,int L,int R) {int lc = o*2 , rc = o*2 + 1;if(y11 <= L && y22 >= R) setv[o] = v;else {pushdown(o);int m = L + (R-L)/2;if(y11 <= m) update(lc,L,m); else maintain(lc,L,m);if(y22 > m) update(rc,m+1,R); else maintain(rc,m+1,R);}maintain(o,L,R);}void query(int o,int L,int R) {if(setv[o] >= 0) {_sum |= setv[o];}else if(y11 <= L && y22 >= R) {_sum |= sumv[o];}else {int m = L + (R-L)/2;if(y11 <= m) query(o*2 , L , m) ;if(y22 > m) query(o*2 + 1, m+1, R);}}int main() {while(~scanf("%d%d",&n,&m)) {if( !n && !m ) return 0;v = 2;y11 = 1; y22 = n;update(1,1,n);while(m–) {scanf("%s",cmd);if(cmd[0] == 'P') {scanf("%d%d%d",&y11,&y22,&c);v = (1<<(c-1));update(1,1,n);}else {scanf("%d%d",&y11,&y22);_sum = 0;query(1,1,n);bool ok = true;for(int i=0;i<30;i++)if(_sum & (1<<i)) {if(ok) printf("%d",i+1);else printf(" %d",i+1);ok = false;}printf("\n");}}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
肯承认错误则错已改了一半
