随手点开一个题。
咦，这不是裸的动态开点线段树吗？写一个写一个……
Code：
#include#include using namespace std;const int N = 3e5 + 5;int n, qn, a[N];inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op;} struct Node { int lc, rc, sum;};namespace PSegT { int root[N], nodeCnt; Node s[N * 80]; #define mid ((l + r) >> 1) void up(int p) { if(p) s[p].sum = s[s[p].lc].sum + s[s[p].rc].sum; } void ins(int &p, int l, int r, int x) { if(!p) p = ++nodeCnt; if(l == x && x == r) { s[p].sum++; return; } if(x <= mid) ins(s[p].lc, l, mid, x); else ins(s[p].rc, mid + 1, r, x); up(p); } void del(int &p, int l, int r, int x) { if(l == x && x == r) { s[p].sum--; if(s[p].sum == 0) p = 0; return; } if(x <= mid) del(s[p].lc, l, mid, x); else del(s[p].rc, mid + 1, r, x); up(p); if(!s[p].lc && !s[p].rc && !s[p].sum) p = 0; } int query(int p, int l, int r, int x, int y) { if(!p) return 0; if(x <= l && y >= r) return s[p].sum; int res = 0; if(x <= mid) res += query(s[p].lc, l, mid, x, y); if(y > mid) res += query(s[p].rc, mid + 1, r, x, y); return res; } } using namespace PSegT;inline void swap(int &x, int &y) { int t = x; x = y; y = t;}int main() { read(n), read(qn); nodeCnt = 0; for(int i = 1; i <= n; i++) { read(a[i]); ins(root[a[i]], 1, n, i); } for(int op; qn--; ) { read(op); if(op == 1) { int x, y, c; read(x), read(y), read(c); printf("%d\n", query(root[c], 1, n, x, y)); } else { int x; read(x); del(root[a[x]], 1, n, x); del(root[a[x + 1]], 1, n, x + 1); swap(a[x], a[x + 1]); ins(root[a[x]], 1, n, x); ins(root[a[x + 1]], 1, n, x + 1); } } return 0;}
写完题的我：
内存太小，差评，卡常数，差评……这sb题……
点开题解：
……大概说的就是我……
没事复杂度其实是一样的
警醒a！！！不要一上手就乱写数据结构……