题目链接
前言
莫队好题，比较板但又比较考转移的思维。
思路
很简单的发现是对操作序列进行莫队。
先对问题进行转换。
首先对于两种修改，第一种修改显然是没有第二种好写的，考虑将第一种转换为第二种。想到对于每一次第一种修改可以单开一个点，将其值赋值为要修改的值，这样就可以将第一种修改转换为第二种修改了，即将赋值转换为这个点与新开的点交换点值，这样方便撤销修改。
接下来就应该考虑 add() 与 del() 的写法了。
由于删除和扩展到的如果是查询点只有加与减的差别。如果是修改点，由于修改的操作时交换，换两次相当于没换，删除和扩展的操作应是一样的。
对于向右扩展与删除，是不会影响到前面的修改的，但对于向左的扩展与删除显然是会的，所以需要分开写。我们假设我们不在 \(a\) 数组上修改，而是在 \(rfl\) 数组上修改，\(rfl_i\) 表示进行一系列的交换后 \(i\) 位置所对应的原来的在 \(a\) 数组上的位置，再开两个数组分别为 \(pos\) 与 \(cnt\)，\(pos_i\) 表示原来 \(a\) 数组上的 \(i\) 位置现在在 \(rfl\) 数组上对应的位置下标，\(cnt_i\) 表示原来的 \(a\) 数组中 \(i\) 的位置在答案中加了几次。
先考虑更简单的向右扩展或删除。
向右扩展显然是在 \(rfl\) 数组 上进行修改。如果扩展到的是查询点，直接修改答案与 \(cnt\) 数组即可。如果扩展到的是修改点，假设交换的位置为 \(u\) 和 \(v\)，直接交换 \(rfl\) 数组上对应位置的值，并且修改 \(pos\) 数组上对应位置的值，即交换 \(rfl_u\) 和 \(rfl_v\) 的值，同时交换 \(pos_{rfl_u}\) 和 \(pos_{rfl_v}\) 的值。
再考虑向左扩展或删除。
显然向左扩展我们应该在 \(a\) 数组 上进行操作，因为向左扩展或删除的操作显然是最先进行的。如果是查询点方法与向右类似，不再多说。如果是修改点，首先应该减去 \(u\) 和 \(v\) 两点对答案的贡献，显然直接交换 \(a\) 的值是不行的，不然多次交换后会出问题。所以我们应该交换其在 \(rfl\) 对应位置上的值，并交换 \(cnt\) 数组上的值。毕竟如果最开始就将两个位置的值交换了，那后续对这两个位置的查询次数显然也是要交换的。总结下来就是要交换 \(pos_u\) 与 \(pos_v\) 的值，交换 \(rfl_{pos_u}\) 与 \(rfl_{pos_v}\) 的值，交换 \(cnt_u\) 与 \(cnt_v\) 的值。
然后外面套个莫队板子就做完了。
关键部分代码
其他都是莫队板子没什么好看的。
struct node1 {int op, u, v;
} b[maxn];
usd answer = 0;
void addl(int i) {if(b[i].op == 0) { int x = b[i].u; answer += a[x], cnt[x]++; AC; }answer -= a[b[i].u] * cnt[b[i].u];answer -= a[b[i].v] * cnt[b[i].v];swap(cnt[b[i].v], cnt[b[i].u]);swap(pos[b[i].u], pos[b[i].v]);swap(rfl[pos[b[i].u]], rfl[pos[b[i].v]]);answer += a[b[i].u] * cnt[b[i].u];answer += a[b[i].v] * cnt[b[i].v];
}
void dell(int i) {if(b[i].op == 0) { int x = b[i].u; answer -= a[x], cnt[x]--; AC; }answer -= a[b[i].u] * cnt[b[i].u];answer -= a[b[i].v] * cnt[b[i].v];swap(cnt[b[i].v], cnt[b[i].u]);swap(pos[b[i].u], pos[b[i].v]);swap(rfl[pos[b[i].u]], rfl[pos[b[i].v]]);answer += a[b[i].u] * cnt[b[i].u];answer += a[b[i].v] * cnt[b[i].v];
}
void addr(int i) {if(b[i].op == 0) { int x = rfl[b[i].u]; answer += a[x], cnt[x]++; AC; }swap(rfl[b[i].u], rfl[b[i].v]);swap(pos[rfl[b[i].u]], pos[rfl[b[i].v]]);
}
void delr(int i) {if(b[i].op == 0) { int x = rfl[b[i].u]; answer -= a[x], cnt[x]--; AC; }swap(rfl[b[i].u], rfl[b[i].v]);swap(pos[rfl[b[i].u]], pos[rfl[b[i].v]]);
}