「NOI2017」整数
有一些比较简单的(log^2n)做法
比如暴力在动态开点线段树上维护每个位置为(0)还是(1)，我们发现涉及到某一位加上(1)或者减去(1)实际上对其他位的影响只有区间覆盖，通过线段树上二分可以得到区间覆盖的位置，然后暴力区间覆盖即可。
反正我这种菜鸡大常数写法只得到了68分..
考虑利用势能，注意到如果同时改变加法和减法，势能很容易被(b)搞掉
如果分开维护加法和减法，把位置上的(1)的个数当做势能，可以发现，暴力修改是均摊(O(nlog a))的
直接暴力维护两个数组(plu)和(dec)
考虑单点求值，因为保证了(xge 0)
所以我们发现只需要两个条件就可以确定第(k)位的值，即
- (ans_1=[plu_k=dec_k])
- (ans_2=[plu[k-1,1]ge[dec[k-1,1]]])，这里是倒着进行字符串比较的意思
第(k)位的答案即为(ans_1 xor ans_2)，这里讨论一下就可以得到了
考虑找到(le p)位置的两个数组第一个不同的位置，然后比较大小
一个暴力的想法是，把每个不同的位置塞到set里面去，然后每次在set里面二分找一下位置，也是(log^2n)的
考虑到每次修改的一个长为(log a)连续的区间(这里实际上饶了一个大圈子)
所以把区间每(log a)分一块，块也是有势能的，然后set里面一次赛一个块就可以了
复杂度就一个(log)了
Code:
#include <cstdio>
#include <cctype>
#include <set>
#include <algorithm>
#define ll long long
using std::min;
const int SIZE=1<<21;
char ibuf[SIZE],*iS,*iT;
//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)
#define gc() getchar()
template <class T>
void read(T &x)
{
int f=0;x=0;char c=gc();
while(!isdigit(c)) f|=c=='-',c=gc();
while(isdigit(c)) x=x*10+c-'0',c=gc();
if(f) x=-x;
}
const int N=1e6+10;
int n,t1,t2,t3;
int plu[N*30],dec[N*30],bel[N*30];
int edt[N],vis[N];
std::set <int> s;
std::set <int>::iterator it;
int qry(int p)
{
while(p%32!=0&&plu[p]==dec[p]) --p;
if(plu[p]!=dec[p])
{
if(plu[p]>dec[p]) return 1;
else return 0;
}
p=bel[p];
it=s.upper_bound(p);
if(s.empty()||it==s.begin()) return 1;
--it;
p=(*it)*32;
while(plu[p]==dec[p]) --p;
if(plu[p]>dec[p]) return 1;
else return 0;
}
int main()
{
read(n),read(t1),read(t2),read(t3);
int m=n*30+31,T=(m-1)/32+1;
for(int L,R=0,i=1;i<=T;i++)
{
L=R+1,R=i*32;
for(int j=L;j<=R;j++) bel[j]=i;
}
for(int op,a,b,k,i=1;i<=n;i++)
{
read(op);
if(op==1)
{
edt[0]=0;
read(a),read(b);
if(a>0)
{
for(int p,j=1;j<=30;j++)
if(a>>j-1&1)
{
p=j+b;
if(vis[bel[p]]!=i)
edt[++edt[0]]=bel[p],vis[bel[p]]=i;
while(plu[p])
{
plu[p++]=0;
if(vis[bel[p]]!=i)
edt[++edt[0]]=bel[p],vis[bel[p]]=i;
}
plu[p]=1;
}
}
else
{
a=-a;
for(int p,j=1;j<=30;j++)
if(a>>j-1&1)
{
p=j+b;
if(vis[bel[p]]!=i)
edt[++edt[0]]=bel[p],vis[bel[p]]=i;
while(dec[p])
{
dec[p++]=0;
if(vis[dec[p]]!=i)
edt[++edt[0]]=bel[p],vis[bel[p]]=i;
}
dec[p]=1;
}
}
for(int j=1;j<=edt[0];j++)
{
int L=(edt[j]-1)*32+1,R=edt[j]*32,flag=1;
for(int l=L;l<=R;l++)
if(plu[l]!=dec[l])
{
flag=0;
break;
}
if(flag)
{
if(s.find(edt[j])!=s.end()) s.erase(edt[j]);
}
else
s.insert(edt[j]);
}
}
else
{
read(k);
int p=k++;
int ans=0;
if(plu[k]==dec[k]) ans=1;
printf("%d
",ans^qry(p));
}
}
return 0;
}
2019.5.31