bzoj4942 [Noi2017]整数

bzoj4942 [Noi2017]整数

​​ 题目背景

在人类智慧的山巅，有着一台字长为

1048576 1048576 位（此数字与解题无关）的超级计算机，著名理论计算机科

学家P博士正用它进行各种研究。不幸的是，这天台风切断了电力系统，超级计算机

无法工作，而 P 博士明天就要交实验结果了，只好求助于学过OI的你… …

题目描述

P 博士将他的计算任务抽象为对一个整数的操作。

具体来说，有一个整数

x x ，一开始为

0 0 。

接下来有

n n 个操作，每个操作都是以下两种类型中的一种：

1 a b：将 x

x 加上整数 a\cdot 2^b

a⋅2b ，其中 a

a 为一个整数， b

b 为一个非负整数 2 k ：询问 x

x 在用二进制表示时，位权为 2^k

2k 的位的值（即这一位上的 1

1 代表 2^k

2k ） 保证在任何时候，

x\geqslant 0 x⩾0 。

输入输出格式

输入格式： 输入的第一行包含四个正整数

n,t_1,t_2,t_3 n,t1​,t2​,t3​ ，

n n 的含义见题目描述，

t_1 t1​ ，

t_2 t2​ ，

t_3 t3​ 的具体含义见子任务。

接下来

n n 行，每行给出一个操作，具体格式和含义见题目描述。

同一行输入的相邻两个元素之间，用恰好一个空格隔开。

输出格式： 对于每个询问操作，输出一行，表示该询问的答案（

0 0 或

1 1 ）。对于加法操作，没有任何输出。

输入输出样例

输入样例#1： 复制

10 3 1 2 1 100 0 1 2333 0 1 -233 0 2 5 2 7 2 15 1 5 15 2 15 1 -1 12 2 15 输出样例#1： 复制

0 1 0 1 0 说明

在所有测试点中，

1\leqslant t_1 \leqslant 3, 1 \leqslant t_2 \leqslant 4, 1 \leqslant t_3 \leqslant 2 1⩽t1​⩽3,1⩽t2​⩽4,1⩽t3​⩽2 。不同的

t_1, t_2, t_3 t1​,t2​,t3​ 对应的特殊限制如下：

对于 t_1 = 1

t1=1 的测试点，满足 a = 1

a=1 对于 t_1 = 2

t1=2 的测试点，满足 |a| = 1

∣a∣=1 对于 t_1 = 3

t1=3 的测试点，满足 |a| \leqslant 10^9

∣a∣⩽109 对于 t_2 = 1

t2=1 的测试点，满足 0 \leqslant b, k \leqslant 30

0⩽b,k⩽30 对于 t_2 = 2

t2=2 的测试点，满足 0 \leqslant b, k \leqslant 100

0⩽b,k⩽100 对于 t_2 = 3

t2=3 的测试点，满足 0 \leqslant b, k \leqslant n

0⩽b,k⩽n 对于 t_2 = 4

t2=4 的测试点，满足 0 \leqslant b, k \leqslant 30n

0⩽b,k⩽30n 对于 t_3 = 1

t3​=1 的测试点，保证所有询问操作都在所有修改操作之后 对于 t_3 = 2

t3​=2 的测试点，不保证询问操作和修改操作的先后顺序 本题共 25 个测试点，每个测试点 4 分。各个测试点的数据范围如下：

考虑利用线段树进行模拟这个过程 因为位数太多 我选择在线段树上一个节点压30位 然后每个节点记录len0,len1表示最长延伸的1或0的长度 我的线段树左边低位右边高位 在左加法的时候将a拆分成两个先加后半部分 如果有进位 那么我就加到前半部分然后再去线段树上加这个节点 如果还有进位我就查询一下最长的连续1延伸到哪里中间全部改成0前面改成1 在查询的时候就类似update的时候一样 如果位置在左边我判断下右边是否连续 如果连续那么我的连续长度就要加上他 然后一路找下去即可

负数的情况 类似整数 首先取绝对值 然后每次改的时候往里面改负数即可

写的时候卡了卡常 然而还是这么慢qwq

感谢pickupwin巨佬帮忙查错 做题debug一天 问了巨佬一下，巨佬就帮我看出来错误了 update 2018 0628更新一下代码风格:

#include#define lc (x<<1)#define rc (x<<1|1)#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e6+10;const int g=30;const int rt=1e6;bool tag[N<<2][2];int len[N<<2][2],v[N<<2];int n,t1,t2,t3,bin[33];inline void pushdown(int x,int l,int r){ int mid=l+r>>1; if (tag[x][0]){ tag[lc][0]=1;tag[lc][1]=0;v[lc]=v[rc]=0;len[lc][0]=mid-l+1;len[lc][1]=0; tag[rc][0]=1;tag[rc][1]=0;len[rc][0]=r-mid;len[rc][1]=0;tag[x][0]=0; } if (tag[x][1]){ tag[lc][1]=1;tag[lc][0]=0;v[lc]=v[rc]=bin[30]-1;len[lc][1]=mid-l+1;len[lc][0]=0; tag[rc][1]=1;tag[rc][0]=0;len[rc][1]=r-mid;len[rc][0]=0;tag[x][1]=0; }}inline void update(int x,int l,int r){ int mid=l+r>>1; len[x][0]=(len[lc][0]==mid-l+1?1:0)*len[rc][0]+len[lc][0]; len[x][1]=(len[lc][1]==mid-l+1?1:0)*len[rc][1]+len[lc][1];}inline void modify(int x,int l,int r,int l1,int r1,int op){ if(l1<=l&&r1>=r){ if (op==1) v[x]=bin[g]-1;else v[x]=0; tag[x][op]=1;tag[x][op^1]=0;len[x][op]=r-l+1;len[x][op^1]=0;return; }int mid=l+r>>1;pushdown(x,l,r); if (l1<=mid) modify(lc,l,mid,l1,r1,op); if (r1>mid) modify(rc,mid+1,r,l1,r1,op);update(x,l,r);}inline int insert1(int x,int l,int r,int p,int v1){ if (l==r){ v[x]+=v1;int flag=0;len[x][0]=len[x][1]=0; if (v[x]>=bin[g]){flag=1;v[x]%=bin[g];} if (v[x]<0){flag=-1;v[x]+=bin[g];} if (v[x]==bin[g]-1) len[x][1]=1;if (!v[x]) len[x][0]=1; return flag; }int mid=l+r>>1;pushdown(x,l,r);int flag=0; if(p<=mid) flag=insert1(lc,l,mid,p,v1); else flag=insert1(rc,mid+1,r,p,v1);update(x,l,r);return flag;}inline int qr(int x,int l,int r,int p,int op){ if (l==r) return len[x][op]; int mid=l+r>>1;pushdown(x,l,r); if (p>mid) return qr(rc,mid+1,r,p,op); else{ int leno=qr(lc,l,mid,p,op); if(leno==mid-p+1) if (len[rc][op]==r-mid) return leno+r-mid;else return leno+len[rc][op]; else return leno; }}inline int query(int x,int l,int r,int p){ if(l==r) return v[x]; int mid=l+r>>1;pushdown(x,l,r); if (p<=mid) return query(lc,l,mid,p); else return query(rc,mid+1,r,p);}inline void build(int x,int l,int r){ if (l==r) {len[x][0]=1;return;} int mid=l+r>>1;build(lc,l,mid); build(rc,mid+1,r);update(x,l,r);}int main(){// freopen("a.in","r",stdin); n=read();t1=read();t2=read();t3=read(); for (int i=0;i<=31;++i) bin[i]=1<>=(g-1)-st+1;fi=-fi;a=-a; }else fi=a%bin[(g-1)-st+1],a>>=(g-1)-st+1; fi=fi*bin[st];a+=insert1(1,0,rt,pos,fi); if (!a) continue;int flag=insert1(1,0,rt,pos+1,a);if(!flag) continue; if (flag==1){ int len1=qr(1,0,rt,pos+2,1);if (len1>=1) modify(1,0,rt,pos+2,pos+2+len1-1,0); insert1(1,0,rt,pos+2+len1,1); }else{ int len0=qr(1,0,rt,pos+2,0);if (len0>=1) modify(1,0,rt,pos+2,pos+2+len0-1,1); insert1(1,0,rt,pos+2+len0,-1); } }else{ int b=read(),pos=b/g,st=b%g;printf("%d\n",(query(1,0,rt,pos)&bin[st])?1:0); } } return 0;}

原来的代码

#include#include#include#include#includeusing namespace std;#define N 1000010#define lc (x<<1)#define rc (x<<1|1)int n0=30;const int full=(1<inline void W(T x) { static int buf[30], cnt; if (x == 0) write_char('0'); else { if (x < 0) write_char('-'), x = -x; for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48; while (cnt) write_char(buf[cnt--]); }}inline void flush() { fwrite(obuf, 1, oh - obuf, stdout);}struct node{ int len0,len1,v,tag;//tag=-1->0 tag=1->full}tree[N<<2];inline void update(int x,int l,int r,int mid){ int len=mid-l+1; tree[x].len0=(tree[lc].len0==len)*tree[rc].len0+tree[lc].len0; tree[x].len1=(tree[lc].len1==len)*tree[rc].len1+tree[lc].len1;}inline void dochange(int x,int l,int r,int v){ if (v==full){ tree[x].v=full;tree[x].len0=0;tree[x].len1=r-l+1;tree[x].tag=2;return; }tree[x].v=0;tree[x].len1=0;tree[x].len0=r-l+1;tree[x].tag=-1;}inline void pushdown(int x,int l,int r){ if (!tree[x].tag) return;int mid=l+r>>1; dochange(lc,l,mid,tree[x].tag==-1?0:full); dochange(rc,mid+1,r,tree[x].tag==-1?0:full); tree[x].tag=0;}inline bool modify(int x,int l,int r,int l1,int r1,int v){ if (l1<=l&&r1>=r){ tree[x].v+=v;bool flag=0;tree[x].len0=tree[x].len1=0; if (tree[x].v>full) tree[x].v&=full,flag=1; if (tree[x].v<0) tree[x].v+=full+1,flag=1; if (tree[x].v==full) tree[x].tag=2,tree[x].len1=r-l+1; if (!tree[x].v) tree[x].tag=-1,tree[x].len0=r-l+1;return flag; }int mid=l+r>>1;pushdown(x,l,r);bool tmp=0; if (l1<=mid) tmp|=modify(lc,l,mid,l1,r1,v); if (r1>mid) tmp|=modify(rc,mid+1,r,l1,r1,v);update(x,l,r,mid);return tmp;}inline void change(int x,int l,int r,int l1,int r1,int v){ if (l1>r1) return; if (l1<=l&&r1>=r) {dochange(x,l,r,v);return;} int mid=l+r>>1;pushdown(x,l,r); if (l1<=mid) change(lc,l,mid,l1,r1,v); if (r1>mid) change(rc,mid+1,r,l1,r1,v);update(x,l,r,mid);}inline bool query(int x,int l,int r,int p,int k){ if(l==r) return (tree[x].v>>k)&1;int mid=l+r>>1;pushdown(x,l,r); if (p<=mid) return query(lc,l,mid,p,k); else return query(rc,mid+1,r,p,k);}inline int lg(int x){ static int cnt;cnt=0;while(x) ++cnt,x>>=1;return cnt;}inline int qr1(int x,int l,int r,int p,int len){ if (l==r) return tree[x].len1==0?0:tree[x].len1+len;int mid=l+r>>1;pushdown(x,l,r); if(p<=mid){ if (tree[rc].len1==r-mid) return qr1(lc,l,mid,p,len+tree[rc].len1); return qr1(lc,l,mid,p,tree[rc].len1); }return qr1(rc,mid+1,r,p,len); }inline int qr0(int x,int l,int r,int p,int len){ if (l==r) return tree[x].len0==0?0:tree[x].len0+len;int mid=l+r>>1;pushdown(x,l,r); if(p<=mid){ if (tree[rc].len0==r-mid) return qr0(lc,l,mid,p,len+tree[rc].len0); return qr0(lc,l,mid,p,tree[rc].len0); }return qr0(rc,mid+1,r,p,len);}inline int abs(int x){return x<0?-x:x;}int n,t1,t2,t3,bin[30];int main(){ //freopen("bzoj4942.in","r",stdin); //freopen("bzoj4942.out","w",stdout); n=read();t1=read();t2=read();t3=read();dochange(1,0,1e6,0); for (int i=0;i<=29;++i) bin[i]=(1<0){ tmp=modify(1,0,1e6,b1,b1,(a&(bin[n0-b2-1]))*(1<>=n0-b2;a+=tmp;if (!a) continue; tmp=modify(1,0,1e6,b1+1,b1+1,a);if (!tmp) continue; r=qr1(1,0,1e6,b1+2,0);change(1,0,1e6,b1+2,b1+2+r-1,0); modify(1,0,1e6,b1+2+r,b1+2+r,1); }else{a=abs(a); tmp=modify(1,0,1e6,b1,b1,-(a&(bin[n0-b2-1]))*(1<>=n0-b2;a+=tmp;if (!a) continue; tmp=modify(1,0,1e6,b1+1,b1+1,-a);if (!tmp) continue; r=qr0(1,0,1e6,b1+2,0);change(1,0,1e6,b1+2,b1+2+r-1,full); modify(1,0,1e6,b1+2+r,b1+2+r,-1); } }else{ k=read();static int tmp; tmp=k/n0;k%=n0;W(query(1,0,1e6,tmp,k));write_char('\n'); } }flush(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。