题解 P3747 【[六省联考2017]相逢是问候】

看到这题题解都是什么线段树维护区间最小修改次数，我来发一波并查集+树状数组的做法。 因为每个数最多被修改$O(\log P)$次，所以对于修改次数达到$\log P$的，我们可以**直接跳过这一个点**。考虑一个暴力，每次修改从$l$到$r$枚举每个点，这样是$O(n^2)$的，但是我们如果能够在每个点$i$处修改完之后直接跳到下一个修改次数未达到上界的点，这样复杂度就是正确的。 考虑一个与BZOJ2054类似的思路，使用并查集来支持这个操作。初始时整个序列每个位置的父亲赋为本身，对于每个修改次数达到上界的点$i$，我们将$i$并到$i+1$上。那么点$i$的下一个未达到上界的点就是$i+1$所在联通块的根(这里一定要注意合并的有序性，要把左边往右边合并) 至于区间求和，树状数组即可。 但是由于本题时间复杂度瓶颈不在于数据结构，所以这对时间的优化可能并没有太大意义……但是至少好写了一些吧 附我的AC代码 ```cpp #include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #define llong long long using namespace std; inline int read() { int x=0; bool f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=0; for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0'); if(f) return x; return -x; } const int N = 5e4; const int B = 20000; llong a[N+3]; llong b[N+3]; llong p[57]; int pos[N+3]; llong bit[N+3]; int uf[N+3]; llong pw[2][B+3][57]; int pwf[2][B+3][57]; int n,q,m; llong c; bool flag; llong quickpow(llong x,llong y,int mod) { int y0 = y%B,y1 = y/B; llong ret = pw[0][y0][mod]*pw[1][y1][mod]; flag |= pwf[0][y0][mod]|pwf[1][y1][mod]|(ret>=p[mod]); return ret%p[mod]; } llong getphi(llong x) { llong ret = x; int i = 2; while(i*i<=x && x>1) { if(x%i==0) { ret = ret/i*(i-1); while(x%i==0) {x/=i;} } i++; } if(x>1) {ret = ret/x*(x-1);} return ret; } int findfa(int u) { int i = u; while(uf[u]!=u) {u = uf[u];} while(uf[i]!=u) { int j = uf[i]; uf[i] = u; i = j; } return u; } void addval(int u,llong x) { while(u<=n) { bit[u] = (bit[u]+x)%p[0]; u+=(u&(-u)); } } llong querysum(int rb) { llong ret = 0ll; while(rb) { ret = (ret+bit[rb])%p[0]; rb -= (rb&(-rb)); } return ret; } llong getval(int y,llong x) { llong ret = x; flag = ret>=p[y]?true:false; ret%=p[y]; if(flag) ret+=p[y]; for(int i=y-1; i>=0; i--) { ret = quickpow(c,ret,i); if(flag) ret+=p[i]; } return ret%p[0]; } int main() { scanf("%d%d%lld%lld",&n,&q,&p[0],&c); while(p[m]!=1) {m++; p[m] = getphi(p[m-1]);} m++; p[m] = 1; for(int i=1; i<=n; i++) {scanf("%lld",&a[i]); a[i] %= p[0]; b[i] = a[i]; addval(i,a[i]); uf[i] = i;} uf[n+1] = n+1; for(int i=0; i<=m; i++) { pw[0][0][i] = 1ll; for(int j=1; j<=B; j++) { pw[0][j][i] = pw[0][j-1][i]*c; pwf[0][j][i] = pwf[0][j-1][i]|(pw[0][j][i]>=p[i]); pw[0][j][i] %= p[i]; } pw[1][0][i] = 1ll; for(int j=1; j<=B; j++) { pw[1][j][i] = pw[1][j-1][i]*pw[0][B][i]; pwf[1][j][i] = pwf[1][j-1][i]|pwf[0][B][i]|(pw[1][j][i]>=p[i]); pw[1][j][i] %= p[i]; } } while(q--) { int opt,lb,rb; scanf("%d%d%d",&opt,&lb,&rb); if(opt==0) { for(int i=findfa(lb); i<=rb; i=findfa(i+1)) { pos[i]++; addval(i,p[0]-b[i]); b[i] = getval(pos[i],a[i]); addval(i,b[i]); if(pos[i]==m) {uf[i] = i+1;} } } else if(opt==1) { llong ans = (querysum(rb)-querysum(lb-1)+p[0])%p[0]; printf("%lld\n",ans); } } return 0; } ```