# NOI2017 Integer Solutions

I wrote an evening commemorating a title $$NOI~d1t1$$.
Title: Maintains a non-negative integer \x\ with a long length of tinea, supporting two operations:

1. Add or subtract $$a\cdot2^b$$ to (x\), where $$ale10^9, ble30n). 2. Ask for the value of bit \(k$$ where $$k\le30n). Analysis: • Let's start with an interesting question: Why is the range of \(b$$ and $$k$$ in \? How did this $$30$$ come about?
• Does this inspire us to divide into n segments, each with 30 bits to maintain?
• And what does every $$30$$ digit mean? Can I just use an $$int$$ variable to store it?
• Take another look at the operation the title requires to support. Does the operation $$1$$ equal adding or subtracting two adjacent paragraphs?
• The general idea is to maintain these $$n$$ in a way that supports single-point modifications when viewed as $$2^{30}$$.
• Unfortunately, it is a headache to move in and out.
• For example, if each of the following consecutive sections is $$1$$, it would be equivalent to turning this section into $$0$$ and then moving to the higher position.
• It can be equivalent to an interval assignment of $$0$$, a single point $$+1$$.
• What about abdication? Is the interval assignment $$1$$, single point $$-1$$?
• Did you think of anything?
• I can segment tree! But I still wrote overnight.
• It is important to note that the segment tree is now maintained not by how many bits per line but by how many bits per $$30$$, so our carry skips start at the place where the carry occurs, and each successive bit is a 1 segment.
• Another question follows. How do we know where the advance will end?
• There are segment trees, can't you just make a segment tree two?
• Simple to say, full of details.
• First, we need to know if each bit of an interval is all $$0$$ or all $$1$$, which can be achieved by maintaining intervals and intervals or by maintaining them.
• Due to the interval coverage operation, we also need to maintain a $$cov$$ marker, but this is a minor problem. How to write the segment tree dichotomy is the key point.
• For example, now we want the first position not to be 2^{30}-1 after a $$(pos)$$.
• If we can enter the left interval query (that is, the left interval is not completely blocked by $$pos$$, we will first query the left interval.
• If it exists, everything will be fine. If it doesn't exist, let's go into the right interval query.
• It looks like the complexity is quite wrong, because it is possible for each node to have its left and right intervals recursive?
• But it's okay, because this process is equivalent to asking for information on the interval $$[pos,n]$$, similar to a regular segment tree, where the complexity of a single operation is $$O(nlogn)$$.
• Take note of the boundary conditions. If rounding occurs in paragraph $$n$$, do we have paragraph $$n+1$$ to receive this information?
• As I write below, the second branch of the segment tree returns to $$n$$, for obvious reasons, let alone say.
• In another case, if each bit of each segment between $$[pos,n]$$, the second branch of the segment tree returns $$-1$$.
• Special judgment of these two cases can be, the specific details or look at the code, there are notes anyway.
• Maybe $$140$$ isn't that long? Welcome to your stepping on the bones.
Click to view the code
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e6+5,all=(1<<30)-1;
int i,m,n;
struct node
{
int l,r,cov;///cov is an interval coverage marker (-1 means no marker)
int sum[2];///sum[0] for interval and sum[1] for interval or
}f[4*maxn];
{
int q=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') q=10*q+ch-'0',ch=getchar();
return q*f;
}
void pushup(int p)
{
f[p].sum[0]=f[2*p].sum[0]&f[2*p+1].sum[0];
f[p].sum[1]=f[2*p].sum[1]|f[2*p+1].sum[1];
}
void pushdown(int p)
{
if(f[p].cov==-1) return ;
f[2*p].cov=f[2*p].sum[0]=f[2*p].sum[1]=f[p].cov;
f[2*p+1].cov=f[2*p+1].sum[0]=f[2*p+1].sum[1]=f[p].cov;
f[p].cov=-1;
}
void build(int p,int l,int r)
{
f[p].l=l,f[p].r=r,f[p].cov=-1;
if(l==r) return ;
int mid=(l+r)/2;
build(2*p,l,mid);
build(2*p+1,mid+1,r);
pushup(p);
}
void cover(int p,int l,int r,int val)
{///Interval Coverage
if(l<=f[p].l&&f[p].r<=r)
{
f[p].cov=f[p].sum[0]=f[p].sum[1]=val;
return ;
}
if(l>f[p].r||r<f[p].l) return ;
pushdown(p);
cover(2*p,l,r,val);
cover(2*p+1,l,r,val);
pushup(p);
}
void modify(int p,int pos,int val)
{///dot plus
if(f[p].l==f[p].r)
{
f[p].sum[0]+=val,f[p].sum[1]+=val;
return ;
}
pushdown(p);
int mid=(f[p].l+f[p].r)/2;
if(pos<=mid) modify(2*p,pos,val);
else modify(2*p+1,pos,val);
pushup(p);
}
int query(int p,int pos)
{///Single point query
if(f[p].l==f[p].r) return f[p].sum[0];
pushdown(p);
int mid=(f[p].l+f[p].r)/2;
if(pos<=mid) return query(2*p,pos);
else return query(2*p+1,pos);
}
int find_nxt(int p,int pos,int opt)
{///Segment Tree Binary, opt=0/1 means to look for the first non-all/0 position after POS (including pos), and -1 means it does not exist
if(opt==0&&f[p].sum[0]==all) return -1;
if(opt==1&&f[p].sum[1]==0) return -1;
if(f[p].l==f[p].r) return f[p].l;
pushdown(p);
int mid=(f[p].l+f[p].r)/2;
if(pos>=mid+1) return find_nxt(2*p+1,pos,opt);///Defined behind pos
if(res!=-1) return res;///Return directly if left subtree exists
return find_nxt(2*p+1,pos,opt);///Otherwise go into the right subtree to find
}
{///In pos first position+val
if(val==0) return ;
int cur=query(1,pos);///The value in this bit before the operation is cur
if(cur+val<=all) modify(1,pos,val);///No carry
else
{
modify(1,pos,val-(1<<30));///Modify the current bit value first
int nxt=find_nxt(1,pos+1,0);
if(nxt>=pos+2) cover(1,pos+1,nxt-1,0);///Intermediate progression equals interval coverage
modify(1,nxt,1);///last one digit 1
}
}
void dec(int pos,int val)
{
if(val==0) return ;
int cur=query(1,pos);
if(cur>=val) modify(1,pos,-val);
else
{
modify(1,pos,(1<<30)-val);
int nxt=find_nxt(1,pos+1,1);
if(nxt>=pos+2) cover(1,pos+1,nxt-1,all);
modify(1,nxt,-1);
}
}
int main()
{
build(1,0,n);
for(i=1;i<=n;i++)
{
if(opt==1)
{
if(a>0)
{
}
else
{
a*=-1;
dec(pos,a<<num&all);///impact on pos position
dec(pos+1,a>>(30-num));///effect on pos+1 bit
}
}
else
{