树状数组套权值线段树
#include#include #include #include #include #include #define E exit(0)using namespace std;#define LL long long#define gc getchar()inline int read() { int x = 0; char c = gc; while(c < '0' || c > '9') c = gc;while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}inline LL read_LL() {LL x = 0; char c = gc; while(c < '0' || c > '9') c = gc;while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}#undef gcconst int N = 5e4 + 10;const int Out = 2147483647;struct Node { int opt, l, r, k;} Ask[N];int n, m;int Num[N << 1], totNum, A[N], Length;int Root[N];int W[N * 125], Lson[N * 125], Rson[N * 125];int Add_root[N], Cut_root[N];int Hjt_;namespace Seg { void Insert(int &rt, int l, int r, int x) { if(!rt) rt = ++ Hjt_; W[rt] ++; if(l == r) return ; int mid = (l + r) >> 1; if(x <= mid) Insert(Lson[rt], l, mid, x); else Insert(Rson[rt], mid + 1, r, x); } int Getrank(int l, int r, int k, int opt) { if(l == r) { if(opt == 0) return 1; int s = 0; for(int i = 1; i <= Add_root[0]; i ++) s += W[Add_root[i]]; for(int i = 1; i <= Cut_root[0]; i ++) s -= W[Cut_root[i]]; return s; } int mid = (l + r) >> 1; if(k <= mid) { for(int i = 1; i <= Add_root[0]; i ++) Add_root[i] = Lson[Add_root[i]]; for(int i = 1; i <= Cut_root[0]; i ++) Cut_root[i] = Lson[Cut_root[i]]; return Getrank(l, mid, k, opt); } else { int sum = 0; for(int i = 1; i <= Add_root[0]; i ++) { sum += W[Lson[Add_root[i]]]; Add_root[i] = Rson[Add_root[i]]; } for(int i = 1; i <= Cut_root[0]; i ++) { sum -= W[Lson[Cut_root[i]]]; Cut_root[i] = Rson[Cut_root[i]]; } int ret = sum + Getrank(mid + 1, r, k, opt); return ret; } } int Getnum(int l, int r, int k) { if(l == r) return l; int mid = (l + r) >> 1; int sum = 0; for(int i = 1; i <= Add_root[0]; i ++) sum += W[Lson[Add_root[i]]]; for(int i = 1; i <= Cut_root[0]; i ++) sum -= W[Lson[Cut_root[i]]]; if(sum >= k) { for(int i = 1; i <= Add_root[0]; i ++) Add_root[i] = Lson[Add_root[i]]; for(int i = 1; i <= Cut_root[0]; i ++) Cut_root[i] = Lson[Cut_root[i]]; Getnum(l, mid, k); } else { for(int i = 1; i <= Add_root[0]; i ++) Add_root[i] = Rson[Add_root[i]]; for(int i = 1; i <= Cut_root[0]; i ++) Cut_root[i] = Rson[Cut_root[i]]; Getnum(mid + 1, r, k - sum); } } void Poi_G(int l, int r, int x, int val) { for(int i = 1; i <= Cut_root[0]; i ++) W[Cut_root[i]] += val; if(l == r) return ; int mid = (l + r) >> 1; if(x <= mid) { for(int i = 1; i <= Cut_root[0]; i ++) { if(Lson[Cut_root[i]] == 0) Lson[Cut_root[i]] = ++ Hjt_; Cut_root[i] = Lson[Cut_root[i]]; } Poi_G(l, mid, x, val); } else { for(int i = 1; i <= Cut_root[0]; i ++) { if(Rson[Cut_root[i]] == 0) Rson[Cut_root[i]] = ++ Hjt_; Cut_root[i] = Rson[Cut_root[i]]; } Poi_G(mid + 1, r, x, val); } } int Asknum(int l, int r, int k) { if(l == r) { int sum = 0; for(int i = 1; i <= Add_root[0]; i ++) sum += W[Add_root[i]]; for(int i = 1; i <= Cut_root[0]; i ++) sum -= W[Cut_root[i]]; k -= sum; if(k > 0) return -1; return l; } int sum = 0; for(int i = 1; i <= Add_root[0]; i ++) sum += W[Lson[Add_root[i]]]; for(int i = 1; i <= Cut_root[0]; i ++) sum -= W[Lson[Cut_root[i]]]; int mid = (l + r) >> 1; if(k <= sum) { for(int i = 1; i <= Add_root[0]; i ++) Add_root[i] = Lson[Add_root[i]]; for(int i = 1; i <= Cut_root[0]; i ++) Cut_root[i] = Lson[Cut_root[i]]; Asknum(l, mid, k); } else { for(int i = 1; i <= Add_root[0]; i ++) Add_root[i] = Rson[Add_root[i]]; for(int i = 1; i <= Cut_root[0]; i ++) Cut_root[i] = Rson[Cut_root[i]]; Asknum(mid + 1, r, k - sum); } }}namespace Bit { inline int Lowbit(int x) { return (x & (-x));} void Add(int rt, int x, int val) { for(int i = rt; i <= n; i += Lowbit(i)) { Seg:: Insert(Root[i], 1, Length, x); } } int Getrank(int l, int r, int k) { Add_root[0] = Cut_root[0] = 0; for(int i = r; i >= 1; i -= Lowbit(i)) Add_root[++ Add_root[0]] = Root[i]; for(int i = l - 1; i >= 1; i -= Lowbit(i)) Cut_root[++ Cut_root[0]] = Root[i]; k = lower_bound(Num + 1, Num + Length + 1, k) - Num; return Seg:: Getrank(1, Length, k, 0); } int Getnum(int l, int r, int k) { Add_root[0] = Cut_root[0] = 0; for(int i = r; i >= 1; i -= Lowbit(i)) { Add_root[++ Add_root[0]] = Root[i]; } for(int i = l - 1; i >= 1; i -= Lowbit(i)) { Cut_root[++ Cut_root[0]] = Root[i]; } return Seg:: Getnum(1, Length, k); } void Poi_G(int x, int k) { Cut_root[0] = 0; for(int i = x; i <= n; i += Lowbit(i)) Cut_root[++ Cut_root[0]] = Root[i]; int a = lower_bound(Num + 1, Num + Length + 1, A[x]) - Num; A[x] = k; Seg:: Poi_G(1, Length, a, -1); Cut_root[0] = 0; for(int i = x; i <= n; i += Lowbit(i)) Cut_root[++ Cut_root[0]] = Root[i]; a = lower_bound(Num + 1, Num + Length + 1, k) - Num; Seg:: Poi_G(1, Length, a, 1); } int Asknum(int l, int r, int k, int opt) { k = lower_bound(Num + 1, Num + Length + 1, k) - Num; int kk = k; Add_root[0] = Cut_root[0] = 0; for(int i = r; i >= 1; i -= Lowbit(i)) Add_root[++ Add_root[0]] = Root[i]; for(int i = l - 1; i >= 1; i -= Lowbit(i)) Cut_root[++ Cut_root[0]] = Root[i]; k = Seg:: Getrank(1, Length, k, 0); Add_root[0] = Cut_root[0] = 0; for(int i = r; i >= 1; i -= Lowbit(i)) Add_root[++ Add_root[0]] = Root[i]; for(int i = l - 1; i >= 1; i -= Lowbit(i)) Cut_root[++ Cut_root[0]] = Root[i]; int k2 = Seg:: Getrank(1, Length, kk, 1); Add_root[0] = Cut_root[0] = 0; for(int i = r; i >= 1; i -= Lowbit(i)) Add_root[++ Add_root[0]] = Root[i]; for(int i = l - 1; i >= 1; i -= Lowbit(i)) Cut_root[++ Cut_root[0]] = Root[i]; if(opt == 1) { if(k == 1) return -1; return Seg:: Asknum(1, Length, k - 1); } else return Seg:: Asknum(1, Length, k2 + 1); }}int main() { n = read(), m = read(); for(int i = 1; i <= n; i ++) Num[i] = read(), A[i] = Num[i]; totNum = n; for(int i = 1; i <= m; i ++) { Ask[i].opt = read(); if(Ask[i].opt != 3) {Ask[i].l = read(), Ask[i].r = read(), Ask[i].k = read();} else Ask[i].l = read(), Ask[i].k = read(), Num[++ totNum] = Ask[i].k; if(Ask[i].opt == 4 || Ask[i].opt == 5) { Num[++ totNum] = Ask[i].k; } } sort(Num + 1, Num + totNum + 1); Length = unique(Num + 1, Num + totNum + 1) - Num - 1; for(int i = 1; i <= n; i ++) { int a = lower_bound(Num + 1, Num + Length + 1, A[i]) - Num; Bit:: Add(i, a, 1); } #define opt Ask[i].opt #define l Ask[i].l #define r Ask[i].r #define k Ask[i].k for(int i = 1; i <= m; i ++) { if(opt == 1) { cout << Bit:: Getrank(l, r, k) << "\n"; } else if(opt == 2) { int ans = Bit:: Getnum(l, r, k); cout << Num[ans] << "\n"; } else if(opt == 3) { Bit:: Poi_G(l, k); } else if(opt == 4) { int ans = Bit:: Asknum(l, r, k, 1); if(ans == -1) cout << "-2147483647" << "\n"; else cout << Num[ans] << "\n"; } else { int ans = Bit:: Asknum(l, r, k, 0); if(ans == -1) cout << "2147483647" << "\n"; else cout << Num[ans] << "\n"; } } return 0;}