codevs_5037 线段树练习4加强版

#include<cstdio> #include<cstring> #define mod 800 using namespace std; int n, m, k, l, r, x; char s[10]; int a[200050], v[251][200050], seg[251]; void read(int &xx) { char tt=getchar();int sx=1; while((tt<'0'||tt>'9')&&tt!='-')tt=getchar(); if(tt=='-'){sx=-1;tt=getchar();} for(xx=0;tt>='0'&&tt<='9';tt=getchar())xx=xx*10+int(tt-'0'); xx*=sx; } int main() { memset(seg,0,sizeof(seg)); scanf("%d%d%d", &n, &m, &k); for(int i=1;i<=n;i++) { read(a[i]); if(a[i]>=k) a[i]%=k; v[(i-1)/mod+1][a[i]]++; } for(int i=1;i<=m;i++) { scanf("%s", &s); scanf("%d%d", &l, &r); if(s[0]=='a') { scanf("%d", &x); int lx=(l-1)/mod+2, rx=(r-1)/mod; if(lx<=rx) { for(int i=lx;i<=rx;i++) { seg[i]+=x; if(seg[i]>=k) seg[i]%=k; } for(int i=l;i<=(lx-1)*mod;i++) { v[lx-1][a[i]]--; a[i]+=x; if(a[i]>=k) a[i]%=k; v[lx-1][a[i]]++; } for(int i=rx*mod+1;i<=r;i++) { v[rx+1][a[i]]--; a[i]+=x; if(a[i]>=k) a[i]%=k; v[rx+1][a[i]]++; } } else for(int i=l;i<=r;i++) { v[(i-1)/mod+1][a[i]]--; a[i]+=x; if(a[i]>=k) a[i]%=k; v[(i-1)/mod+1][a[i]]++; } } else { int ans=0; int lx=(l-1)/mod+2, rx=(r-1)/mod; if(lx<=rx) { for(int i=lx;i<=rx;i++) { int yu; if(k<seg[i]) yu=k-seg[i]%k; else yu=k-seg[i]; if(k==yu) yu=0; ans+=v[i][yu]; } for(int i=l;i<=(lx-1)*mod;i++) if(a[i]+seg[lx-1]==k||a[i]+seg[lx-1]==0) ans++; for(int i=rx*mod+1;i<=r;i++) if(a[i]+seg[rx+1]==k||a[i]+seg[rx+1]==0) ans++; } else for(int i=l;i<=r;i++) if(a[i]+seg[(i-1)/mod+1]==0||a[i]+seg[(i-1)/mod+1]==k) ans++; printf("%d\n", ans); } } return 0; } #include<cstdio> #include<cstring> #define mod