求大爷教线段树怎么写啊QAQ
只会写分块...一开始脑抽写成了O(NKlogN)还被CZL大爷嘲讽了一发T T
f[i][j]表示在第i块中，模k为j的数有几个，然后每次修改的时候只需要打个标记，查询的时候直接加上标记查就行了
#include#include #include #include #include using namespace std;const int maxn=200010;int n,m,k,blo,x,y,z;int a[maxn],bl[maxn],blcnt[510][maxn],bl2[maxn],bltag[maxn],bltag2[maxn];char s[233];inline void read(int &k){ int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f;}#define update(x) x>=k&&(x-=k)inline void change(int x,const int &delta){ int now=a[x]; blcnt[bl[x]][now]--; now+=delta;update(now); blcnt[bl[x]][now]++; a[x]+=delta;update(a[x]);}inline void add(int l,int r,const int &delta){ for(int i=l;i<=min(r,bl[l]*blo);i++)change(i,delta); if(bl[l]!=bl[r])for(int i=(bl[r]-1)*blo+1;i<=r;i++)change(i,delta); for(int i=bl[l]+1;i
