洛谷3822 [NOI2017] 整数【线段树】【位运算】

题目分析：

首先这题的询问和位(bit)有关，不难想到是用线段树维护位运算。

现在我们压32位再来看这道题。

对于一个加法操作，它的添加位置可以得到，剩下的就是做不超过32的位移。这样根据压位的理论。它最多只会对线段树的两个叶子产生影响，我们分开来考虑两个叶子。

对于一个加法的进位，它实际就是把它之后连续的全为1的位赋值成0，然后更改第一个不是全为1的位，不难想到用lazytag实现。

减法操作与加法操作相反。所以我们要两个标记和两个lazy标记。

对于一个询问，在线段树上查找即可。

代码:

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 const int base = 32;
  5 
  6 int n,maxx;
  7 
  8 struct SEGT{
  9     unsigned int dt;
 10     bool lazy0,lazy1;
 11     bool all0,all1;
 12 }T[(1<<22)];
 13 
 14 void build_tree(int now,int l,int r){
 15     T[now].all0 = 1;
 16     if(l == r) return;
 17     int mid = (l+r)/2;
 18     build_tree(now<<1,l,mid);
 19     build_tree(now<<1|1,mid+1,r);
 20 }
 21 
 22 void push_down0(int now){
 23     T[now<<1].all0 = 1; T[now<<1].all1 = 0;
 24     T[now<<1].lazy0 = 1; T[now<<1].lazy1 = 0;
 25     T[now<<1|1].all0 = 1; T[now<<1|1].all1 = 0;
 26     T[now<<1|1].lazy0 = 1; T[now<<1|1].lazy1 = 0;
 27     T[now<<1].dt = 0; T[now<<1|1].dt = 0; T[now].lazy0 = 0;
 28 }
 29 
 30 void push_down1(int now){
 31     T[now<<1].all1 = 1; T[now<<1].all0 = 0;
 32     T[now<<1].lazy1 = 1; T[now<<1].lazy0 = 0;
 33     T[now<<1|1].all1 = 1; T[now<<1|1].all0 = 0;
 34     T[now<<1|1].lazy1 = 1; T[now<<1|1].lazy0 = 0;
 35     T[now<<1].dt = (1ll<<32)-1; T[now<<1|1].dt = (1ll<<32)-1; T[now].lazy1 = 0;
 36 }
 37 
 38 void push_up(int now){
 39     if(T[now<<1].all0 && T[now<<1|1].all0) T[now].all0 = 1; else T[now].all0 = 0;
 40     if(T[now<<1].all1 && T[now<<1|1].all1) T[now].all1 = 1; else T[now].all1 = 0;
 41 }
 42 
 43 void leafpd(int now){
 44     if(T[now].dt == 0) T[now].all0 = 1; else T[now].all0 = 0;
 45     if(T[now].dt == (1ll<<32)-1) T[now].all1 = 1; else T[now].all1 = 0;
 46 }
 47 
 48 int tag = 0;
 49 void uppaint(int now,int tl,int tr,int place){
 50     if(tl != tr && T[now].lazy0) push_down0(now);
 51     if(tl != tr && T[now].lazy1) push_down1(now);
 52     if(tl >= place){
 53     if(T[now].all1){
 54         T[now].all0 = 1;T[now].all1 = 0;
 55         T[now].lazy0 = 1;T[now].lazy1 = 0;
 56         T[now].dt = 0;
 57         return;
 58     }else{
 59         if(tl == tr){T[now].dt++;tag = 1;leafpd(now);return;}
 60         int mid = (tl+tr)/2;
 61         uppaint(now<<1,tl,mid,place);
 62         if(!tag) uppaint(now<<1|1,mid+1,tr,place);
 63         push_up(now);
 64     }
 65     }else{
 66     int mid = (tl+tr)/2;
 67     if(place > mid) uppaint(now<<1|1,mid+1,tr,place);
 68     else{
 69         uppaint(now<<1,tl,mid,place);
 70         if(!tag) uppaint(now<<1|1,mid+1,tr,place);
 71     }
 72     push_up(now);
 73     }
 74 }
 75 
 76 void downpaint(int now,int tl,int tr,int place){
 77     if(tl != tr && T[now].lazy0) push_down0(now);
 78     if(tl != tr && T[now].lazy1) push_down1(now);
 79     if(tl >= place){
 80     if(T[now].all0){
 81         T[now].all1 = 1;T[now].all0 = 0;
 82         T[now].lazy1 = 1;T[now].lazy0 = 0;
 83         T[now].dt = (1ll<<32)-1;
 84         return;
 85     }else{
 86         if(tl == tr){T[now].dt--;tag=1;leafpd(now);return;}
 87         int mid = (tl+tr)/2;
 88         downpaint(now<<1,tl,mid,place);
 89         if(!tag) downpaint(now<<1|1,mid+1,tr,place);
 90         push_up(now);
 91     }
 92     }else{
 93     int mid = (tl+tr)/2;
 94     if(place > mid) downpaint(now<<1|1,mid+1,tr,place);
 95     else{
 96         downpaint(now<<1,tl,mid,place);
 97         if(!tag) downpaint(now<<1|1,mid+1,tr,place);
 98     }
 99     push_up(now);
100     }
101 }
102 
103 void TModify(int now,int tl,int tr,int place,long long data){
104     if(tl == tr){
105     if(data >= 0){
106         long long res = data + T[now].dt;
107         T[now].dt = (res&((1ll<<32)-1));
108         if(res >= (1ll<<32)){ tag = 0;uppaint(1,0,n,place+1);}
109     }else{
110         long long res = T[now].dt + data;
111         if(res >= 0) T[now].dt = res;
112         else{
113         T[now].dt = res + (1ll<<32);
114         tag = 0;downpaint(1,0,n,place+1);
115         }
116     }
117     leafpd(now);
118     return;
119     }
120     if(T[now].lazy0) push_down0(now);
121     if(T[now].lazy1) push_down1(now);
122     int mid = (tl+tr)/2;
123     if(place <= mid) TModify(now<<1,tl,mid,place,data);
124     else TModify(now<<1|1,mid+1,tr,place,data);
125     push_up(now);
126 }
127 
128 void Modify(){
129     int dr,data,bit; scanf("%d%d",&data,&bit);
130     if(data < 0) dr = -1; else dr = 1;
131     data = abs(data);
132     int a1 = bit>>5,a2 = bit&31;
133     if((1ll*data<<a2) >= (1ll<<32)){
134     long long fw = 1ll*data<<a2;
135     TModify(1,0,n,a1,(fw&((1ll<<32)-1))*dr);
136     fw >>= 32;
137     TModify(1,0,n,a1+1,fw*dr);
138     }else{
139     TModify(1,0,n,a1,(1ll*data<<a2)*dr);
140     }
141 }
142 
143 int QTree(int now,int tl,int tr,int place,int bit){
144     if(T[now].all0) return 0; if(T[now].all1) return 1;
145     if(tl == tr){ if(T[now].dt & (1<<bit)) return 1; else return 0; }
146     int mid = (tl+tr)/2;
147     if(place <= mid) return QTree(now<<1,tl,mid,place,bit);
148     else return QTree(now<<1|1,mid+1,tr,place,bit);
149 }
150 
151 void Query(){
152     int kth; scanf("%d",&kth);
153     int a1 = kth>>5,a2 = kth&31;
154     printf("%d
",QTree(1,0,n,a1,a2));
155 }
156 
157 void work(){
158     for(int i=1;i<=n;i++){
159     int cas; scanf("%d",&cas);
160     if(cas == 1){Modify();}
161     else Query();
162     }
163 }
164 
165 int main(){
166     scanf("%d",&n); int x; scanf("%d%d%d",&x,&x,&x);
167     build_tree(1,0,n);
168     work();
169     return 0;
170 }

洛谷3822 [NOI2017] 整数 【线段树】【位运算】

洛谷3822 [NOI2017] 整数【线段树】【位运算】