AK (HG 2018.10.5 T3)

  题目名字有点骚啊。。 蒟蒻不会分块，所以就打了线段树，代码及其丑。。然后大数据要4s。。（时限5s） 用脚想想也知道这题直接暴力线段树会T的不成样子，那么怎么优化呢？ 我们这时候盯上了这个奇怪的模数，我们发现最多修改60次这个数就绝对不会再变了，为什么呢？证明如下   那么就这样。。好像树状数组也可以。。 那么我丑陋的线段树。。 ``` #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define int long long using namespace std; const int mod=2305843008676823040; int read() { int x=0,f=0;char c=getchar(); while(c<'0' || c>'9' && c!='-') c=getchar(); if(c=='-') f=1,c=getchar(); while(c>='0' && c<='9') x=x*10+c-'0',c=getchar(); return x; } void write(int x) { if(x/10!=0) write(x/10); putchar('0'+x%10); } int n,m; struct Tree { int l,r,sum,f,cnt; }tr[1000010]; void pushup(int x) { tr[x].sum=(tr[x*2].sum%mod+tr[x*2+1].sum%mod)%mod; tr[x].cnt=min(tr[x*2].cnt,tr[x*2+1].cnt); } void build(int x,int l,int r) { if(l==r) { int tmp=read(); tr[x].l=l,tr[x].r=r; tr[x].sum=tmp;tr[x].f=0; tr[x].cnt=0; return; } int mid=(l+r)/2; build(x*2,l,mid); build(x*2+1,mid+1,r); tr[x].l=l,tr[x].r=r,pushup(x); } int query(int x,int l,int r) { if(l>r) return 0; if(l==tr[x].l && r==tr[x].r) {return tr[x].sum;} int mid=(tr[x].l+tr[x].r)/2; if(mid<l) return query(x*2+1,l,r); else if(mid>r) return query(x*2,l,r); else return (query(x*2,l,mid)+query(x*2+1,mid+1,r))%mod; } int Moti(int x,int k) { if(k==0) return 0; if(k==1) return x; int res=0,tmp=Moti(x,k/2)%mod; if(k%2) res=x%mod; res=(res+tmp*2%mod)%mod; return res; } void moti(int x,int l,int r) { if(l>r) return; if(tr[x].cnt>=60) return; if(tr[x].l==tr[x].r) { tr[x].sum=Moti(tr[x].sum,tr[x].sum)%mod; tr[x].cnt++; return; } int mid=(tr[x].l+tr[x].r)/2; if(mid<l) moti(x*2+1,l,r); else if(mid>r) moti(x*2,l,r); else moti(x*2,l,mid),moti(x*2+1,mid+1,r); pushup(x); } signed main() { n=read(),m=read(); build(1,1,n); while(m--) { int l=read(),r=read(); write(query(1,l,r)),puts(""); moti(1,l,r); } return 0; } ```