【CodeChef】 Queries on the String

2019-04-13 16:51发布

站内文章 / 模拟电子
12324 0 1303
前缀和（均摊复杂度可以水过） #include using namespace std; char inc; #define gc() getchar() #define isd(_t) isdigit(_t) inline void get(int& x) { x =0 ;inc=gc(); while(!isd(inc))inc=gc(); while(isd(inc)) { x=x*10+inc-'0'; inc=gc(); } } const int maxn = 100010; int n,m,a[maxn],sum[maxn]; int main() { int op,x,y; get(n);get(m); for(int i=1;i<=n;i++)scanf("%1d",&a[i]),sum[i]=sum[i-1]+a[i],sum[i]%=3,a[i]%=3; for(int i=1;i<=m;i++) { get(op),get(x),get(y); if(op==1) { for(int j=x+1;j<=n;j++)sum[j]=(sum[j]+y-a[x]+3)%3; sum[x]=(sum[x-1]+y)%3; } else { int ans = 0; for(int j=x;j<=y;j++) { for(int k=x;k<=j;k++) { if((sum[j]-sum[k-1]+3)%3==0)ans++; } } printf("%d ",ans); } } return 0; }
如果a,b满足前缀和取模相等，则a+1~b的和取模等于0 显然可以用线段树维护区间 前缀和取模为0，1，2的数量 单点修改区间查询
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 #include #include #include #include #include #include #include #include #include #define pa pair #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char a[100005]; struct data{ int l,r,sum,v[3]; }t[400005]; int n,K; data merge(data a,data b) { data t;t.l=a.l;t.r=b.r; t.sum=a.sum+b.sum; for(int i=0;i<3;i++) { int tmp=(a.sum+i)%3; t.v[tmp]=a.v[tmp]+b.v[i]; } return t; } void build(int k,int l,int r) { t[k].l=l;t[k].r=r;int mid=(l+r)>>1; if(l==r){t[k].sum=(a[l]-'0')%3;t[k].v[t[k].sum]=1;return;} build(k<<1,l,mid);build(k<<1|1,mid+1,r); t[k]=merge(t[k<<1],t[k<<1|1]); } data query(int k,int x,int y) { int l=t[k].l,r=t[k].r,mid=(l+r)>>1; if(l==x&&y==r)return t[k]; if(y<=mid)return query(k<<1,x,y); else if(x>mid)return query(k<<1|1,x,y); else return merge(query(k<<1,x,mid),query(k<<1|1,mid+1,y)); } void change(int k,int x,int val) { int l=t[k].l,r=t[k].r,mid=(l+r)>>1; if(l==r) { t[k].v[0]=t[k].v[1]=t[k].v[2]=0; t[k].v[val%3]=1; t[k].sum=val%3; return; } if(x<=mid)change(k<<1,x,val); else change(k<<1|1,x,val); t[k]=merge(t[k<<1],t[k<<1|1]); } int main() { n=read();K=read(); scanf("%s",a+1); build(1,1,n); while(K--) { int opt=read(),x=read(),y=read(); if(opt==1)change(1,x,y); else { ll ans=0;data t=query(1,x,y); for(int i=0;i<3;i++)ans+=(ll)t.v[i]*(t.v[i]-1)/2; ans+=t.v[0]; printf("%lld ",ans); } } return 0; }

热门文章