CF1588F Jumping Through the Array

https://www.luogu.com.cn/problem/CF1588F

之前见过类似的套路，不过是用来优化空间的，就是莫队的时候分几块来分别跑

要说的话更加类似$KD?tree$每$\sqrt{n}$次操作后重构？

考虑每根号次操作放一起处理

把操作$2,3$涉及到的点设为关键点，不难发现，这个在一个环上，这个关键点到上一个关键点之前到贡献是一样的，可以缩成一个点

就像这样，缩完点之后就只有$\sqrt{n}$个点了，那么询问的时候就只需要枚举每一个点，然后在这个集合里面二分，求出个数再乘上这个点的加法标记即可，单次时间复杂度$\sqrt{n}logn$

对于操作二，暴力修改这个环（缩完点之后的）的所有点的加法标记即可，单次复杂度$\sqrt{n}$
对于操作三，直接$swap$,因为也就$\sqrt{n}$个点，这个操作并没有什么影响，单次$o(1)$

通过调整块大小可以把$log$扔进根号里面，不过这个已经能过了
预处理前缀和还可以做到去掉$log$
code:

#include<bits/stdc++.h>
#define ll long long
#define N 200050
using namespace std;
struct Q {
    int o, x, y;
} q[N];
int vis[N], col[N], viss[N], py[N], p[N], fr[N], gs, n, m;
ll a[N], tg[N], sa[N];
vector<int> v[N];
void dfs(int i, int co) {
    do {
    col[i] = co;i = fr[i];} while(!col[i]);
}
ll calcc(int id, int l, int r) {
    r = upper_bound(v[id].begin(), v[id].end(), r) - v[id].begin() - 1;l = lower_bound(v[id].begin(), v[id].end(), l) - v[id].begin() - 1;// printf("* %d %d %lld %d\n", l, r, tg[id], id);return 1ll * (r - l) *  tg[id];
}
void dfss(int x, int o) {
    int y = x;while(!viss[x]) {
    //printf("*%d %d*", x, p[py[x]]);viss[x] = 1;tg[x] += o;x = col[p[py[x]]];}x = y;while(viss[x]) viss[x] = 0, x = col[p[py[x]]];
}
void calc() {
    if(!gs) return;int ctot = 0;for(int i = 0; i <= n; i ++) {
    tg[i] = sa[i] = col[i] = py[i] = vis[i] = 0;vector<int> o;v[i].swap(o);}for(int i = 1; i <= n; i ++) sa[i] = sa[i - 1] + a[i];for(int i = 1; i <= gs; i ++) {
    if(q[i].o == 2) col[q[i].x] = q[i].x;if(q[i].o == 3) col[q[i].x] = q[i].x, col[q[i].y] = q[i].y;}for(int i = 1; i <= n; i ++) if(col[i] == i) dfs(i, i);for(int i = 1; i <= n; i ++) if(col[i] && !vis[col[i]]) vis[col[i]] = ++ ctot, py[ctot] = col[i];for(int i = 1; i <= n; i ++) col[i] = vis[col[i]];for(int i = 1; i <= n; i ++) v[col[i]].push_back(i);for(int i = 1; i <= ctot; i ++) sort(v[i].begin(), v[i].end());// printf("*** %d\n", gs);// for(int i = 1; i <= n; i ++) printf("%d ", p[i]); printf("\n");// for(int i = 1; i <= n; i ++) printf("%d ", fr[i]); printf("\n");// for(int i = 1; i <= n; i ++) printf("%d ", col[i]); printf("\n");// for(int i = 1; i <= ctot; i ++) printf("%d ", py[i]); printf("\n");// for(int i = 1; i <= ctot; i ++) {
    // for(int x : v[i]) printf(" %d ", x); printf("\n");// } printf("----\n");for(int i = 1; i <= gs; i ++) {
    int o = q[i].o, x = q[i].x, y = q[i].y;if(o == 1) {
    ll ans = sa[y] - sa[x - 1];for(int i = 1; i <= ctot; i ++) ans += calcc(i, x, y);printf("%lld\n", ans);} else if(o == 2) {
    dfss(col[x], y);} else if(o == 3) {
    // printf("& %d %d\n", x, y);swap(fr[p[x]], fr[p[y]]);swap(p[x], p[y]);}}for(int i = 1; i <= n; i ++) a[i] += tg[col[i]];gs = 0;
}
int main() {
    // freopen("a.in","r",stdin);// freopen("a.out","w",stdout);scanf("%d", &n);for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);for(int i = 1; i <= n; i ++) scanf("%d", &p[i]), fr[p[i]] = i;scanf("%d", &m);int blo = sqrt(m); gs = 0;for(int i = 1; i <= m; i ++) {
    gs ++;scanf("%d%d%d", &q[gs].o, &q[gs].x, &q[gs].y);if(gs % blo == 0) calc();}calc();return 0;
}