CDQ分治&整体二分学习个人小结

目录

• 小结
• CDQ分治
  • 二维LIS
  • 第一道裸题 bzoj1176 Mokia
  • bzoj3262 陌上花开
  • bzoj 1790 矩形藏宝地
  • hdu5126四维偏序
  • P3157 [CQOI2011]动态逆序对
    • CDQ
    • 树套树
    • bzoj1176 树套树但是我过不了
  • CF 762E
    • CDQ写法
    • 树套树写法
  • CSUSTOJ 1024：CDQ
  • CSUSTOJ 1026：强制在线树套树
• 整体二分
  • 动态区间第k小
  • P3332 [ZJOI2013]K大数查询

初学推荐博客：LemonMZc BraketBN Owen_codeisking

CDQ&整体二分教程和题目：Winniechen

1

小结

CDQ分治

二维LIS

如果你还没学过CDQ分治，可以先忽略这题。。。呃

• 首先这题一看就是一个三维偏序的裸题，不过普通CDQ分治的写法会wa，因为求LIS是有后效性的。
• 我们不能先解决左边，再解决右边，最后合并，
• 比如：定义\(dp[i]\)表示以\(i\)结尾的元素的LIS的长度。
• 但是他只能记录末位置，而不知道从哪些地方转移来。
• 如果在一次合并前就解决了子区间\([mid+1,r]\)区间内的情况，这次合并就算重复的贡献。
• 因此，我们需要先解决左边，向右边转移后，再解决右边。

AC_Code

const int MXN = 1e5 + 7;
const int MXE = 1e6 + 7;
int n, m;
pii ar[MXN];
struct lp {
    int fi, se, val, id;
}cw[MXN];
int ans;
bool cmp(const lp&a, const lp&b) {
    return a.se < b.se;
}
bool cmp2(const lp&a, const lp&b) {
    return a.id < b.id;
}
int bit[MXN];
int N;
void bit_add(int x, int v) {
    while(x <= N) {
        bit[x] = big(bit[x], v);
        x += lowbit(x);
    }
}
void bit_clr(int x) {
    while(x <= N) {
        bit[x] = 0;
        x += lowbit(x);
    }
}
int bit_query(int x) {
    int ans = 0;
    while (x > 0) {
        ans = big(ans, bit[x]);
        x -= lowbit(x);
    }
    return ans;
}
void solve(int l, int r) {
    if(l >= r) return;
    int mid = (l + r) >> 1;
    solve(l, mid);
    sort(cw + l, cw + mid + 1, cmp);
    sort(cw + mid + 1, cw + r + 1, cmp);
    int i = l;
    for(int j = mid + 1; j <= r; ++j) {
        for(; i <= mid && cw[i].se < cw[j].se; ++i) bit_add(cw[i].fi, cw[i].val);
        cw[j].val = big(cw[j].val, bit_query(cw[j].fi - 1) + 1);
    }
    for(-- i; i >= l; --i) bit_clr(cw[i].fi);
//    inplace_merge(cw + l, cw + mid + 1, cw + r + 1, cmp);
    sort(cw + mid + 1, cw + r + 1, cmp2);
    solve(mid + 1, r);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("/home/cwolf9/CLionProjects/ccc/in.txt", "r", stdin);
//    freopen("/home/cwolf9/CLionProjects/ccc/out.txt", "w", stdout);
#endif
//    int tim = 1;
    n = read();
    vector<int> vs;
    for(int i = 1; i <= n; ++i) {
        ar[i].fi = read(), ar[i].se = read();
        vs.eb(ar[i].fi);
    }
    my_unique(vs);
    for(int i = 1; i <= n; ++i) {
        ar[i].fi = lower_bound(all(vs), ar[i].fi) - vs.begin() + 1;
        cw[i].fi = ar[i].fi, cw[i].se = ar[i].se, cw[i].val = 1, cw[i].id = i;
    }
    N = vs.size() + 1;
    ans = 1;
    solve(1, n);
    for(int i = 1; i <= n; ++i) ans = big(ans, cw[i].val);
    printf("%d\n", ans);
    return 0;
}

第一道裸题 bzoj1176 Mokia

/*
2000000的矩阵，单点更新，区间查询
一维时间，一维x，树状数组维护y
*/
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long LL;

const int MXN = 2e6 + 6;
const int INF = 0x3f3f3f3f;

int n, k, s, cnt;
LL ans[MXN];
struct lp {
    int x, y, ip, idx, delta;
}cw[MXN];
bool cmp(const lp &a, const lp &b) {
    return a.x < b.x ||(a.x == b.x && a.y < b.y);
}
LL bit[MXN];
int lowbit(int x){return (x&(-x));}
void add(int x,int c){for(;x <= n;x += lowbit(x)) bit[x]+=c;}
LL query(int x){LL ans = 0;for(;x;x -= lowbit(x))ans+=bit[x];return ans;}
void cdq(int l, int r) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    cdq(l, mid); cdq(mid+1,r);
    int j = l;
    for(int i = mid+1; i <= r; ++i) {
        if(cw[i].ip == 2) {
            for(; j <= mid && cw[j].x <= cw[i].x; ++j) {
                if(cw[j].ip == 1) add(cw[j].y, cw[j].delta);
            }
            ans[cw[i].idx] += cw[i].delta * query(cw[i].y);
        }
    }
    for(-- j; j >= l; --j) if(cw[j].ip == 1) add(cw[j].y, -cw[j].delta);
    inplace_merge(cw+l,cw+mid+1,cw+r+1, cmp);
}
int main() {
    scanf("%d%d", &s, &n);
    cnt = 0;
    int cntp = 0, x, y, a, b;
    while(scanf("%d", &k) == 1 && k != 3) {
        if(k == 1) {
            scanf("%d%d%d", &x, &y, &a);
            ++ cnt;
            cw[cnt] = {x, y, 1, cnt, a};
        }else {
            scanf("%d%d%d%d", &x, &y, &a, &b);
            ++ cntp; ans[cntp] = (1LL*a - x)*(b - y)*s;
            ++ cnt; cw[cnt] = {x-1, y-1, 2, cntp, 1};
            ++ cnt; cw[cnt] = {x-1, b, 2, cntp, -1};
            ++ cnt; cw[cnt] = {a, y-1, 2, cntp, -1};
            ++ cnt; cw[cnt] = {a, b, 2, cntp, 1};
        }
    }
    cdq(1, cnt);
    for(int i = 1; i <= cntp; ++i) printf("%lld\n", ans[i]);
    return 0;
}

---

bzoj3262 陌上花开

/*
简单地说，对于每个点求出x,y,z都小于等于它的点的个数
一维x，一维y，树状数组维护z
*/
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long LL;

const int MXN = 2e6 + 6;
const int INF = 0x3f3f3f3f;

int n, s;
struct lp {
    int x, y, z, ip, cnt, ans;
}cw[MXN], temp[MXN];
bool cmpx(const lp &a, const lp &b) {
    return a.x < b.x ||(a.x == b.x && a.y < b.y)||(a.x == b.x && a.y == b.y && a.z < b.z);
}
bool cmpyz(const lp &a, const lp &b) {
    return a.y < b.y||(a.y == b.y && a.z < b.z);
}
int bit[MXN];
int lowbit(int x){return (x&(-x));}
void add(int x,int c){for(;x <= s;x += lowbit(x)) bit[x]+=c;}
int query(int x){int ans = 0;for(;x;x -= lowbit(x))ans+=bit[x];return ans;}
void cdq(int l,int r) {
    if(l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid); cdq(mid+1, r);
    //sort(cw + l, cw + 1 + mid, cmpyz);
    //sort(cw + 1 + mid, cw + 1 + r, cmpyz);
    int j = l;
    for(int i = mid+1; i <= r; ++i) {
        for(; j <= mid && cw[j].y <= cw[i].y; ++j) {
            add(cw[j].z, cw[j].cnt);
        }
        cw[i].ans += query(cw[i].z);
    }
    for(-- j; j >= l; --j) add(cw[j].z, -cw[j].cnt);
    int p1 = l, p2 = mid+1, cnt = l;
    while(p1 <= mid && p2 <= r) {
        if(p1 <= mid && cw[p1].y <= cw[p2].y) temp[cnt++] = cw[p1], ++ p1;
        else temp[cnt++] = cw[p2], ++ p2;
    }
    while(p1 <= mid) temp[cnt++] = cw[p1], ++ p1;
    while(p2 <= r) temp[cnt++] = cw[p2], ++ p2;
    for(int i = l; i <= r; ++i) cw[i] = temp[i];
}
int main() {
    scanf("%d%d", &n, &s);
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &cw[i].x, &cw[i].y, &cw[i].z);
        cw[i].ip = i; cw[i].ans = 0;
    }
    sort(cw + 1, cw + 1 + n, cmpx);
    int cnt = 1, p = 0;
    for(int i = 2; i <= n; ++i) {
        if(cw[i].x!=cw[i-1].x||cw[i].y!=cw[i-1].y||cw[i].z!=cw[i-1].z) {
            cw[++p] = cw[i-1];
            cw[p].cnt = cnt;
            cnt = 1;
            if(i == n) {
                cw[++p] = cw[i];
                cw[p].cnt = cnt;
            }
        }else {
            ++ cnt;
            if(i == n) {
                cw[++p] = cw[i-1];
                cw[p].cnt = cnt;
            }
        }
    }
    cdq(1, p);
    for(int i = 1; i <= p; ++i) bit[cw[i].ans+cw[i].cnt-1] += cw[i].cnt;
    for(int i = 0; i < n; ++i) printf("%d\n", bit[i]);
    return 0;
}

---

bzoj 1790 矩形藏宝地

/*
对每个点询问是否存在一个点a,b小于等于它，c,d大于等于它
一维c，一维d，离散化a，线段树维护a上的b
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int INF = 0x3f3f3f3f;
const int MXN = 1e6 + 6;

int n, m, k, ans;
struct lp {
    int a, b, c, d, ans;
}cw[MXN], temp[MXN];
int ar[MXN], sum[MXN<<2];
bool cmpc(const lp &A, const lp &B) {
    return A.c > B.c;
}
bool cmpd(const lp &A, const lp &B) {
    return A.d > B.d;
}
void update(int p,int val,int l,int r,int rt) {
    if(l == r) {
        sum[rt] = val;
        return ;
    }
    int mid = (l + r) >> 1;
    if(p <= mid) update(p, val, l, mid, rt<<1);
    else update(p, val, mid+1, r, rt<<1|1);
    sum[rt] = min(sum[rt<<1], sum[rt<<1|1]);
}
int query(int L,int R,int l,int r,int rt) {
    if(L <= l && r <= R) {
        return sum[rt];
    }
    int mid = (l + r) >> 1;
    if(L > mid) return query(L,R,mid+1,r,rt<<1|1);
    else if(R <= mid) return query(L,R,l,mid,rt<<1);
    else {
        return min(query(L,mid,l,mid,rt<<1),
            query(mid+1,R,mid+1,r,rt<<1|1));
    }
}
void cdq(int l,int r) {
    if(l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid); cdq(mid+1, r);
    int j = l;
    for(int i = mid+1; i <= r; ++i) {
        for(; j <= mid && cw[j].d >= cw[i].d; ++j) {
            update(cw[j].a, cw[j].b, 1, k, 1);
        }
        if(query(1,cw[i].a,1,k,1) <= cw[i].b) cw[i].ans = 1;
    }
    for(-- j; j >= l; --j) update(cw[j].a, INF, 1, k, 1);
    int p1 = l, p2 = mid+1, cnt = l;
    while(p1 <= mid && p2 <= r) {
        if(p1 <= mid && cw[p1].d >= cw[p2].d) temp[cnt++] = cw[p1], ++ p1;
        else temp[cnt++] = cw[p2], ++ p2;
    }
    while(p1 <= mid) temp[cnt++] = cw[p1], ++ p1;
    while(p2 <= r) temp[cnt++] = cw[p2], ++ p2;
    for(int i = l; i <= r; ++i) cw[i] = temp[i];
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d%d%d", &cw[i].a, &cw[i].b, &cw[i].c, &cw[i].d);
        ar[i] = cw[i].a; cw[i].ans = 0;
    }
    memset(sum, 0x3f, sizeof(sum));
    sort(ar+1, ar+1+n);
    k = unique(ar+1,ar+1+n) - ar;
    sort(cw + 1, cw + 1 + n, cmpc);
    for(int i = 1; i <= n; ++i) {
        cw[i].a = lower_bound(ar+1,ar+k,cw[i].a) - ar;
        cw[i].c = i;
    }
    cdq(1, n);
    for(int i = 1; i <= n; ++i) ans += cw[i].ans;
    printf("%d\n", ans);
    return 0;
}

---

hdu5126四维偏序

/*
三维空间n次操作，更新一个点，查询两点的长方体间点的个数
CDQ套CDQ：一维时间，一维x，再一维y，树状数组维护z
每次查询，三维容斥一下，分成8个区间的查询
*/
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long LL;

const int MXN = 2e6 + 6;
const int INF = 0x3f3f3f3f;

int n, tot, k;
struct lp {
    int x, y, z, flag, idx, ip, delta;
}cw[MXN], temp[MXN], Tmp[MXN];
int ans[MXN], ar[MXN];
int bit[MXN];
int lowbit(int x){return (x&(-x));}
void add(int x,int c){for(;x <= 400006;x += lowbit(x)) bit[x]+=c;}
int query(int x){int ANs = 0;for(;x;x -= lowbit(x))ANs+=bit[x];return ANs;}
void cdq2(int l,int r) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    cdq2(l, mid); cdq2(mid+1, r);
    int j = l;
    for(int i = mid+1; i <= r; ++i) {
        for(; j <= mid && temp[j].y <= temp[i].y; ++j)
            if(temp[j].ip == 1&&temp[j].flag == 0) add(temp[j].z, 1);
        if(temp[i].ip == 2&&temp[i].flag == 1) {
            ans[temp[i].idx] += query(temp[i].z)*temp[i].delta;
        }
    }
    for(-- j; j >= l; --j) if(temp[j].ip == 1&&temp[j].flag == 0) add(temp[j].z, -1);
    int p1 = l, p2 = mid+1, cnt = l;
    while(p1 <= mid && p2 <= r) {
        if(temp[p1].y <= temp[p2].y) {
            Tmp[cnt++] = temp[p1]; ++ p1;
        }else {
            Tmp[cnt++] = temp[p2]; ++ p2;
        }
    }
    while(p1 <= mid) {
        Tmp[cnt++] = temp[p1]; ++ p1;
    }
    while(p2 <= r) {
        Tmp[cnt++] = temp[p2]; ++ p2;
    }
    for(int i = l; i <= r; ++i) temp[i] = Tmp[i];
}
void cdq1(int l,int r) {
    if(l == r) return ;
    int mid = (l + r) >> 1;
    cdq1(l, mid); cdq1(mid+1, r);
    int p1 = l, p2 = mid+1, cnt = l;
    while(p1 <= mid && p2 <= r) {
        if(cw[p1].x <= cw[p2].x) {
            temp[cnt++] = cw[p1]; ++ p1;
            temp[cnt-1].flag = 0;
        }else {
            temp[cnt++] = cw[p2]; ++ p2;
            temp[cnt-1].flag = 1;
        }
    }
    while(p1 <= mid) {
        temp[cnt++] = cw[p1]; ++ p1;
        temp[cnt-1].flag = 0;
    }
    while(p2 <= r) {
        temp[cnt++] = cw[p2]; ++ p2;
        temp[cnt-1].flag = 1;
    }
    for(int i = l; i <= r; ++i) cw[i] = temp[i];
    cdq2(l, r);
}
int main() {
    int tim; scanf("%d", &tim);
    while(tim --) {
        scanf("%d", &n);
        tot = 0;
        int totp = 0;
        for(int i = 0; i < n; ++i) {
            int opt, x1, y1, z1, x2, y2, z2;
            scanf("%d%d%d%d", &opt, &x1, &y1, &z1);
            if(opt == 1) {
                ++ tot; cw[tot] = {x1, y1, z1, 0, 0, 1, 0};
            }else {
                scanf("%d%d%d", &x2, &y2, &z2);
                ++ totp;
                ++ tot; cw[tot] = {x2, y2, z2, 0, totp, 2, 1};
                ++ tot; cw[tot] = {x1-1, y2, z2, 0, totp, 2, -1};
                ++ tot; cw[tot] = {x2, y1-1, z2, 0, totp, 2, -1};
                ++ tot; cw[tot] = {x2, y2, z1-1, 0, totp, 2, -1};
                ++ tot; cw[tot] = {x1-1, y1-1, z2, 0, totp, 2, 1};
                ++ tot; cw[tot] = {x1-1, y2, z1-1, 0, totp, 2, 1};
                ++ tot; cw[tot] = {x2, y1-1, z1-1, 0, totp, 2, 1};
                ++ tot; cw[tot] = {x1-1, y1-1, z1-1, 0, totp, 2, -1};
            }
        }
        for(int i = 1; i <= tot; ++i) ar[i] = cw[i].z;
        sort(ar+1, ar+1+tot);
        k = unique(ar+1, ar+1+tot) - ar;
        for(int i = 1; i <= tot; ++i) cw[i].z = lower_bound(ar+1, ar+k, cw[i].z)-ar;
        cdq1(1, tot);
        for(int i = 1; i <= totp; ++i) printf("%d\n", ans[i]), ans[i] = 0;
    }
    return 0;
}

---

P3157 [CQOI2011]动态逆序对

CDQ

/*
给1到n的一个排列，按某顺序依次删除m个元素，求在每次删除一个元素之前序列的逆序对数。
*/
//对不起，我太暴力了
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int MXN = 1e5 + 6;
const int INF = 0x3f3f3f3f;

int n, m;
LL tot;
struct lp {
    int x, tim, pos;
    LL ans;
}cw[MXN], temp[MXN], Tmp[MXN];
LL ans[MXN], ar[MXN];
LL bit[MXN];
int lowbit(int x){return (x&(-x));}
void ADD(int x,int c){for(; x <= n; x += lowbit(x)) bit[x]+=c;}
LL QUERY(int x){LL ANS = 0;for(; x; x -= lowbit(x)) ANS+=bit[x];return ANS;}
bool cmppos(const lp &a, const lp &b) {
    return a.pos > b.pos;
}
void cdq1(int l,int r) {//求出每个数左边有多少个时间比你大的且值比你大的数
    if(l == r) return ;
    int mid = (l + r) >> 1;
    cdq1(l, mid); cdq1(mid+1, r);
    int j = l;
    for(int i = mid + 1; i <= r; ++i) {
        for(; j <= mid && cw[j].tim >= cw[i].tim; ++j) {
            if(cw[j].tim) ADD(cw[j].x, 1);
        }
        cw[i].ans += QUERY(n) - QUERY(cw[i].x);
    }
    for(-- j; j >= l; --j) if(cw[j].tim) ADD(cw[j].x, -1);
    int p1 = l, p2 = mid+1, cnt = l;
    while(p1 <= mid && p2 <= r) {
        if(cw[p1].tim >= cw[p2].tim) temp[cnt++] = cw[p1], ++p1;
        else temp[cnt++] = cw[p2], ++ p2;
    }
    while(p1 <= mid) temp[cnt++] = cw[p1], ++p1;
    while(p2 <= r) temp[cnt++] = cw[p2], ++ p2;
    for(int i = l; i <= r; ++i) cw[i] = temp[i];
}
void cdq2(int l,int r) {//求出每个数右边有多少个时间比你大的且值比你小的数
    if(l == r) return ;
    int mid = (l + r) >> 1;
    cdq2(l, mid); cdq2(mid+1, r);
    int j = l;
    for(int i = mid + 1; i <= r; ++i) {
        for(; j <= mid && cw[j].tim >= cw[i].tim; ++j) {
            if(cw[j].tim) ADD(cw[j].x, 1);
        }
        cw[i].ans += QUERY(cw[i].x);
    }
    for(-- j; j >= l; --j) if(cw[j].tim) ADD(cw[j].x, -1);
    int p1 = l, p2 = mid+1, cnt = l;
    while(p1 <= mid && p2 <= r) {
        if(cw[p1].tim >= cw[p2].tim) temp[cnt++] = cw[p1], ++p1;
        else temp[cnt++] = cw[p2], ++ p2;
    }
    while(p1 <= mid) temp[cnt++] = cw[p1], ++p1;
    while(p2 <= r) temp[cnt++] = cw[p2], ++ p2;
    for(int i = l; i <= r; ++i) cw[i] = temp[i];
}
void cdq(int l,int r) {
    if(l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid); cdq(mid+1, r);
    int p1 = l, p2 = mid+1, cnt = l;
    while(p1 <= mid && p2 <= r) {
        if(cw[p1].x <= cw[p2].x) temp[cnt++] = cw[p1], ++p1;
        else temp[cnt++] = cw[p2], ++ p2, tot += mid-p1+1;
    }
    while(p1 <= mid) temp[cnt++] = cw[p1], ++p1;
    while(p2 <= r) temp[cnt++] = cw[p2], ++ p2;
    for(int i = l; i <= r; ++i) cw[i] = temp[i];
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &cw[i].x);
        cw[i].tim = 0;
        cw[i].ans = 0;
        ar[cw[i].x] = i;
        cw[i].pos = i;
    }
    for(int i = 1, x; i <= m; ++i) {
        scanf("%d", &x);
        cw[ar[x]].tim = i;
    }
    cdq(1, n);
    sort(cw + 1, cw + 1 + n, cmppos);
    reverse(cw + 1, cw + 1 + n);
    for(int i = 1; i <= n; ++i) {
        if(cw[i].tim == 0) {
            ADD(cw[i].x, 1);
        }else {
            ans[cw[i].tim] += QUERY(n) - QUERY(cw[i].x);
        }
    }
    memset(bit, 0, sizeof(LL)*(n+10));
    for(int i = n; i >= 1; --i) {
        if(cw[i].tim == 0) {
            ADD(cw[i].x, 1);
        }else {
            ans[cw[i].tim] += QUERY(cw[i].x);
        }
    }
    memset(bit, 0, sizeof(LL)*(n+10));
    cdq1(1, n);
    for(int i = 1; i <= n; ++i) {
        ans[cw[i].tim] += cw[i].ans;
        cw[i].ans = 0;
    }
    sort(cw + 1, cw + 1 + n, cmppos);
    cdq2(1, n);
    for(int i = 1; i <= n; ++i) {
        ans[cw[i].tim] += cw[i].ans;
    }
    printf("%lld\n", tot);
    for(int i = 1; i < m; ++i) {
        tot -= ans[i];
        printf("%lld\n", tot);
    }
    return 0;
}

树套树

/*
树状数组套权值线段树
这东西是干什么的呢？
个人感觉大概就是把那种O(n)*O(1)的复杂度优化成O(log)*O(log)的复杂度
比如n个位置，每个位置一个值，查询是O(1)的；log个位置(树状数组)，查询是O(log)的(权值线段树/主席树)
本题把每次询问拆分成两个前缀和相减，然后用树套树优化，树状数组每个节点维护的范围不变，然后将节点变成权值线段树，就是本题的做法。
*/
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long LL;

const int MXN = 2e5 + 6;
const int MXE = 6e6 + 6;
const int INF = 0x3f3f3f3f;

int n, m;
struct lp {
    int l, r;
    LL sum;
}cw[MXE], temp[MXN], Tmp[MXN];
int lb[MXN], rs[MXN], ar[MXN], bel[MXN];
int Root[MXN], NODE, A[MXE], B[MXE];
LL bit[MXN];
int lowbit(int x){return (x&(-x));}
void ADD(int x,int c){for(; x <= n; x += lowbit(x)) bit[x]+=c;}
LL QUERY(int x){LL ANS = 0;for(; x; x -= lowbit(x)) ANS+=bit[x];return ANS;}

bool cmppos(const lp &a, const lp &b) {
    return a.sum > b.sum;
}
void update(int &cur, int x, int l, int r) {
    if(!cur) {
        cur = ++ NODE;
        cw[cur].l = cw[cur].r = 0;
    }
    ++ cw[cur].sum;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(x <= mid) update(cw[cur].l, x, l, mid);
    else update(cw[cur].r, x, mid+1, r);
}
LL Find(int l,int r,int lw,int up,int rt) {
    if(lw <= l && r <= up) {
        return cw[rt].sum;
    }
    if(lw > r || up < l) return 0;
    int mid = (l + r) >> 1;
    if(lw > mid) return Find(mid+1, r, lw, up, cw[rt].r);
    else if(up <= mid) return Find(l, mid, lw, up, cw[rt].l);
    return Find(l, mid, lw, mid, cw[rt].l)+Find(mid+1,r,mid+1,up,cw[rt].r);
}
LL query(int l,int r,int lw,int up) {
    if(lw > up) return 0;
    if(l >= r) return 0;
    A[0] = B[0] = 0;
    for(; r; r -= lowbit(r)) A[++A[0]] = Root[r];//树状数组的求和，每个节点都是一个权值线段树，每个节点的查询时O(log)的
    for(; l; l -= lowbit(l)) B[++B[0]] = Root[l];
    LL ans = 0;
    for(int i = 1; i <= A[0]; ++i) ans += Find(1,n,lw,up,A[i]);
    for(int i = 1; i <= B[0]; ++i) ans -= Find(1,n,lw,up,B[i]);
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &ar[i]);
        bel[ar[i]] = i;
    }
    LL tot = 0;
    for(int i = 1; i <= n; ++i) {
        lb[i] = QUERY(n) - QUERY(ar[i]);
        ADD(ar[i], 1);
        tot += lb[i];
        cw[i].l = cw[i].r = 0;
    }
    memset(bit, 0, sizeof(LL)*(n+5));
    for(int i = n; i >= 1; --i) {
        rs[i] = QUERY(ar[i]-1);
        ADD(ar[i], 1);
    }
    memset(bit, 0, sizeof(LL)*(n+5));
    printf("%lld\n", tot);
    NODE = n;
    for(int i = 1, x; i < m; ++i) {
        scanf("%d", &x);
        tot -= (lb[bel[x]] + rs[bel[x]] - query(0,bel[x]-1,x+1,n) - query(bel[x],n,1,x-1));
        printf("%lld\n", tot);
        for(int y = bel[x]; y <= n; y += lowbit(y)) {//将所有包含bel[x]位置的权值线段树更新
            update(Root[y], x, 1, n);
        }
    }
    scanf("%d", &m);
    return 0;
}
//这样写跑的快一点
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long LL;

const int MXN = 2e5 + 6;
const int MXE = 6e6 + 6;
const int INF = 0x3f3f3f3f;

int n, m;
struct lp {
    int l, r;
    LL sum;
}cw[MXE], temp[MXN], Tmp[MXN];
int lb[MXN], rs[MXN], ar[MXN], bel[MXN];
int Root[MXN], NODE, A[MXE], B[MXE];
LL bit[MXN];
int lowbit(int x){return (x&(-x));}
void ADD(int x,int c){for(; x <= n; x += lowbit(x)) bit[x]+=c;}
LL QUERY(int x){LL ANS = 0;for(; x; x -= lowbit(x)) ANS+=bit[x];return ANS;}

bool cmppos(const lp &a, const lp &b) {
    return a.sum > b.sum;
}
void update(int &cur, int x, int l, int r) {
    if(!cur) {
        cur = ++ NODE;
        cw[cur].l = cw[cur].r = 0;
    }
    ++ cw[cur].sum;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(x <= mid) update(cw[cur].l, x, l, mid);
    else update(cw[cur].r, x, mid+1, r);
}
LL queryda(int l,int r,int x) {
    if(l >= r) return 0;
    A[0] = B[0] = 0;
    for(; r; r -= lowbit(r)) A[++A[0]] = Root[r];
    for(; l; l -= lowbit(l)) B[++B[0]] = Root[l];
    LL ans = 0;
    l = 1, r = n;
    int mid;
    while(l + 1 <= r) {
        mid = (l + r) >> 1;
        if(x <= mid) {
            for(int i = 1; i <= A[0]; ++i) ans += cw[cw[A[i]].r].sum;
            for(int i = 1; i <= B[0]; ++i) ans -= cw[cw[B[i]].r].sum;
            for(int i = 1; i <= A[0]; ++i) A[i] = cw[A[i]].l;
            for(int i = 1; i <= B[0]; ++i) B[i] = cw[B[i]].l;
            r = mid;
        }else {
            for(int i = 1; i <= A[0]; ++i) A[i] = cw[A[i]].r;
            for(int i = 1; i <= B[0]; ++i) B[i] = cw[B[i]].r;
            l = mid + 1;
        }
    }
    return ans;
}
LL queryxiao(int l,int r,int x) {
    if(l >= r) return 0;
    A[0] = B[0] = 0;
    for(; r; r -= lowbit(r)) A[++A[0]] = Root[r];
    for(; l; l -= lowbit(l)) B[++B[0]] = Root[l];
    LL ans = 0;
    l = 1, r = n;
    int mid;
    x - 1;
    while(l + 1 <= r) {
        mid = (l + r) >> 1;
        if(x >= mid + 1) {
            for(int i = 1; i <= A[0]; ++i) ans += cw[cw[A[i]].l].sum;
            for(int i = 1; i <= B[0]; ++i) ans -= cw[cw[B[i]].l].sum;
            for(int i = 1; i <= A[0]; ++i) A[i] = cw[A[i]].r;
            for(int i = 1; i <= B[0]; ++i) B[i] = cw[B[i]].r;
            l = mid + 1;
        }else {
            for(int i = 1; i <= A[0]; ++i) A[i] = cw[A[i]].l;
            for(int i = 1; i <= B[0]; ++i) B[i] = cw[B[i]].l;
            r = mid;
        }
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &ar[i]);
        bel[ar[i]] = i;
    }
    LL tot = 0;
    for(int i = 1; i <= n; ++i) {
        lb[i] = QUERY(n) - QUERY(ar[i]);
        ADD(ar[i], 1);
        tot += lb[i];
        cw[i].l = cw[i].r = 0;
    }
    memset(bit, 0, sizeof(LL)*(n+5));
    for(int i = n; i >= 1; --i) {
        rs[i] = QUERY(ar[i]-1);
        ADD(ar[i], 1);
    }
    memset(bit, 0, sizeof(LL)*(n+5));
    printf("%lld\n", tot);
    NODE = n;
    for(int i = 1, x; i < m; ++i) {
        scanf("%d", &x);
        tot -= (lb[bel[x]]+rs[bel[x]]-queryda(0,bel[x]-1,x)-queryxiao(bel[x],n,x));
        printf("%lld\n", tot);
        for(int y = bel[x]; y <= n; y += lowbit(y)) {
            update(Root[y], x, 1, n);
        }
    }
    scanf("%d", &m);
    return 0;
}

---

bzoj1176 树套树但是我过不了

我不会平衡树昂，就不能让我套个线段树吗？你疯狂给我mle&re是个啥意思？难度要去学平衡树吗？。。不，我不学。。。难受啊

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MXN = 2e5 + 5;
const int MXE = 1e7 + 3e6 + 6;
const int INF = 0x3f3f3f3f;
int n, m;
int s, p, k;
int Root[MXN], NODE;
int ar[MXN], br[MXN];
struct lp {
    int x, y, X, Y, idx;
}cw[MXN];
struct tree {
    int l, r, sum;
}edge[MXE];
int lowbit(int x){return (x&(-x));}
void update(int &p, int pos, int x, int l, int r) {
    if(!p) {
        p = ++ NODE;
        edge[p].l = edge[p].r = edge[p].sum = 0;
    }
    edge[p].sum += x;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(pos <= mid) update(edge[p].l, pos, x, l, mid);
    else update(edge[p].r, pos, x, mid+1, r);
}
int query(int L, int R, int l, int r, int rt) {
    if(L <= l && r <= R) {
        return edge[rt].sum;
    }
    if(L > r || R < l) return 0;
    int mid = (l + r) >> 1;
    if(L > mid) return query(L, R, mid + 1, r, edge[rt].r);
    else if(R <= mid) return query(L, R, l, mid, edge[rt].l);
    return query(L,mid,l,mid,edge[rt].l)+query(mid+1,R,mid+1,r,edge[rt].r);
}
int CALC(int X, int Y) {
    int ans = 0;
    if(X == 0 || Y == 0) return ans;
    for(int u = X; u; u -= lowbit(u)) {
        ans += query(1, Y, 1, p, Root[u]);
    }
    return ans;
}
int main() {
    scanf("%d%d", &s, &m);
    int tot;
    for(int i = 1;; ++ i) {
        tot = i;
        scanf("%d", &cw[i].idx);
        if(cw[i].idx == 1) {
            scanf("%d%d", &cw[i].x, &cw[i].y);
            scanf("%d", &cw[i].X);
        }else if(cw[i].idx == 2) {
            scanf("%d%d", &cw[i].x, &cw[i].y);
            scanf("%d%d", &cw[i].X, &cw[i].Y);
        }else break;
    }
    -- tot;
    k = 0, p = 0;
    for(int i = 1; i <= tot; ++i) {
        ar[++ k] = cw[i].x;
        if(cw[i].idx == 2) ar[++ k] = cw[i].X;
        br[++ p] = cw[i].y;
        if(cw[i].idx == 2) br[++ p] = cw[i].Y;
    }
    sort(ar + 1, ar + k + 1);
    sort(br + 1, br + p + 1);
    k = unique(ar + 1, ar + k + 1) - ar;
    p = unique(br + 1, br + p + 1) - br;
    NODE = p-1;
    for(int i = 1; i <= tot; ++i) {
        cw[i].x = lower_bound(ar + 1, ar + k, cw[i].x)-ar;
        cw[i].y = lower_bound(br + 1, br + p, cw[i].y)-br;
        if(cw[i].idx == 1) {
            for(int y = cw[i].x; y <= k; y += lowbit(y)) {
                update(Root[y], cw[i].y, cw[i].X, 1, p);
            }
        }else {
            cw[i].X = lower_bound(ar + 1, ar + k, cw[i].X)-ar;
            cw[i].Y = lower_bound(br + 1, br + p, cw[i].Y)-br;
            printf("%d\n", CALC(cw[i].X, cw[i].Y)-CALC(cw[i].X,cw[i].y-1)
                -CALC(cw[i].x-1,cw[i].Y)+CALC(cw[i].x-1,cw[i].y-1));
        }
    }
    return 0;
}

---

CF 762E

CDQ写法

/*
转化为二维单点更新区间求和
*/
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long LL;

const int MXN = 2e6 + 5;
const int MXE = 1e7 + 3e6 + 6;
const int INF = 0x3f3f3f3f;

int n, m, N, k, cnt;
LL Ans;
struct lh {
    int x, r, f;
}edge[MXN];
struct lp {
    int flag, x, y, idx, delta;
}cw[MXN], temp[MXN];
int ar[MXN], ans[MXN];
bool cmp(const lh &a, const lh &b) {
    return a.r > b.r;
}
int bit[MXN];
int lowbit(int x){return (x&(-x));}
void ADD(int x,int c,int N){for(; x <= N; x += lowbit(x)) bit[x]+=c;}
int QUERY(int x){if(x<=0)return 0;int ANS = 0;for(; x; x -= lowbit(x)) ANS+=bit[x];return ANS;}

void solve(int l, int r) {
    if(l == r) return ;
    int mid = (l + r) >> 1;
    solve(l, mid); solve(mid + 1, r);
    int j = l;
    for(int i = mid + 1; i <= r; ++i) {
        for(; j <= mid && cw[j].x <= cw[i].x; ++j) {
            if(cw[j].flag == 0) ADD(cw[j].y, 1, N);
        }
        if(cw[i].flag) Ans += QUERY(cw[i].y)*cw[i].delta;
    }
    for(-- j; j >= l; -- j) if(cw[j].flag == 0) ADD(cw[j].y, -1, N);
    int p1 = l, p2 = mid + 1, CNT = l;
    while(p1 <= mid && p2 <= r) {
        if(cw[p1].x <= cw[p2].x) temp[CNT++] = cw[p1], ++p1;
        else temp[CNT++] = cw[p2], ++p2;
    }
    while(p1 <= mid) temp[CNT++] = cw[p1], ++p1;
    while(p2 <= r) temp[CNT++] = cw[p2], ++p2;
    for(int i = l; i <= r; ++i) cw[i] = temp[i];
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &edge[i].x, &edge[i].r, &edge[i].f);
        ++ edge[i].f; N = max(N, edge[i].f + m + 1);
    }
    sort(edge + 1, edge + 1 + n, cmp);
    for(int i = 1, a, b, c, d; i <= n; ++i) {
        a = edge[i].x-edge[i].r;b = edge[i].x+edge[i].r;
        c = max(edge[i].f - m, 1); d = edge[i].f + m;//(a, c), (b, d)
        ++cnt; cw[cnt] = {1, b, d, i, 1};
        ++cnt; cw[cnt] = {1, a-1, d, i, -1};
        ++cnt; cw[cnt] = {1, b, c-1, i, -1};
        ++cnt; cw[cnt] = {1, a-1, c-1, i, 1};
        ++cnt; cw[cnt] = {0, edge[i].x, edge[i].f, i, 0};
    }
    solve(1, cnt);
    printf("%lld\n", Ans);
    return 0;
}

树套树写法

/*
由于本题f的变化范围只有10，所以建普通权值线段树，然后暴力查询21次就行。
但是如果f的变化范围很大的话，可能必须得cdq分治或树套树才能写，下面是树套树代码，原理和动态逆序对那题一样。
*/
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long LL;

const int MXN = 5e5 + 5;
const int MXE = 1e7 + 6;
const int INF = 0x3f3f3f3f;

int n, m, k, N;
LL Ans;
struct lh {
    int x, r, f;
}edg[MXN];
struct lp {
    int l, r, sum;
}cw[MXE];
int Root[MXN], NODE;
int ar[MXN], ans[MXN];
bool cmp(const lh &a, const lh &b) {
    return a.r > b.r;
}
int bit[MXN];
int lowbit(int x){return (x&(-x));}
void ADD(int x,int c,int N){for(; x <= N; x += lowbit(x)) bit[x]+=c;}
int QUERY(int x){if(x<=0)return 0;int ANS = 0;for(; x; x -= lowbit(x)) ANS+=bit[x];return ANS;}

void update(int &p, int x, int l, int r) {
    if(!p) p = ++ NODE;
    ++ cw[p].sum;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) update(cw[p].l, x, l, mid);
    else update(cw[p].r, x, mid+1, r);
}
int query(int rt, int L, int R, int l, int r) {
    if(rt == 0) return 0;
    if(L <= l && r <= R) {
        return cw[rt].sum;
    }
    if(L > r || R < l) return 0;
    int mid = (l + r) >> 1;
    if(L > mid) return query(cw[rt].r, L, R, mid+1, r);
    else if(R <= mid) return query(cw[rt].l, L, R, l, mid);
    else {
        return query(cw[rt].l, L, mid, l, mid) + query(cw[rt].r, mid+1, R, mid + 1, r);
    }
}
int calc(int a, int b, int l, int r) {
    int ans = 0;
    for(; a; a -= lowbit(a)) ans -= query(Root[a], l, r, 1, k);
    for(; b; b -= lowbit(b)) ans += query(Root[b], l, r, 1, k);
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &edg[i].x, &edg[i].r, &edg[i].f);
        ar[++k] = edg[i].x; ar[++k] = edg[i].x-edg[i].r;
        ar[++k] = edg[i].x+edg[i].r; N = max(N, edg[i].f + m);
    }
    sort(edg + 1, edg + 1 + n, cmp);
    sort(ar + 1, ar + 1 + k);
    k = unique(ar + 1, ar + 1 + k) - ar;
    for(int i = 1, l, r; i <= n; ++i) {
        l = lower_bound(ar + 1, ar + k, edg[i].x-edg[i].r) - ar;
        r = lower_bound(ar + 1, ar + k, edg[i].x+edg[i].r) - ar;
        Ans += calc(max(1, edg[i].f-m)-1, edg[i].f + m, l, r);
        l = lower_bound(ar + 1, ar + k, edg[i].x) - ar;
        for(int u = edg[i].f; u <= N; u += lowbit(u)) {
            update(Root[u], l, 1, k);
        }
    }
    printf("%lld\n", Ans);
    return 0;
}

---

CSUSTOJ 1024：CDQ

#include<bits/stdc++.h>
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;

const int INF = 0x3f3f3f3f;
const int MXN = 3e6 + 6;

int n, m;
struct lp {
    int ip, x, p, delta, id;
}cw[MXN], temp[MXN];
struct node {
    int opt, x, y, old;
}Fk[MXN];
int ALL;
int ar[MXN], ANS[MXN], QWE[MXN], sum[MXN<<2], br[MXN], is[MXN];
int bit[MXN];
int lowbit(int x){return (x&(-x));}
void bit_add(int x,int c){for(;x <= n+1;x += lowbit(x)) bit[x]^=c;}
int bit_query(int x){int ans = 0;for(;x;x -= lowbit(x))ans^=bit[x];return ans;}
void update(int p,int val,int l,int r,int rt) {
    is[p] += val;
    return;
}
int query(int p,int l,int r,int rt) {
    return is[p];
}
void cdq(int l, int r) {
    if(l == r) return ;
    //printf("[%d, %d]\n", l, r);
    int mid = (l + r) >> 1;
    cdq(l, mid); cdq(mid+1, r);
    int j = l;
    for(int i = mid+1; i <= r; ++i) {
        for(; j <= mid && cw[j].p <= cw[i].p; ++j) {
            if(cw[j].ip == 1) {
                if(cw[j].id != -1) update(cw[j].id, -1, 1, ALL, 1);
                update(cw[j].x, 1, 1, ALL, 1);
            }
        }
        if(cw[i].ip == 2) {
            ANS[cw[i].id] += cw[i].delta*query(cw[i].x, 1, ALL, 1);
            //printf("%d %d %d %d*\n", cw[i].id, cw[i].delta*query(cw[i].x, 1, ALL, 1), cw[i].x, cw[i].delta);
        }
    }
    for(-- j; j >= l; --j) if(cw[j].ip == 1) {
            if(cw[j].id != -1) update(cw[j].id, 1, 1, ALL, 1);
            update(cw[j].x, -1, 1, ALL, 1);
        }
    int p1 = l, p2 = mid+1, cnt = l;
    while(p1 <= mid && p2 <= r) {
        if(p1 <= mid && cw[p1].p <= cw[p2].p) temp[cnt++] = cw[p1], ++ p1;
        else temp[cnt++] = cw[p2], ++ p2;
    }
    while(p1 <= mid) temp[cnt++] = cw[p1], ++ p1;
    while(p2 <= r) temp[cnt++] = cw[p2], ++ p2;
    for(int i = l; i <= r; ++i) cw[i] = temp[i];
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("E://ADpan//in.in", "r", stdin);
    freopen("E://ADpan//out.out", "w", stdout);
#endif
    //printf("%d\n", (int)(200000*log(1000000)*log(1000000)));
    std::vector<int> vs;
    vs.eb(-1);
    scanf("%d%d", &n, &m);
    assert(n >= 1); assert(n <= 1000000);
    assert(m >= 1); assert(m <= 100000);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &ar[i]), bit_add(i, ar[i]), vs.eb(ar[i]), br[i] = ar[i];
        assert(ar[i] >= 0); assert(ar[i] <= 1000000000);
    }
    for(int i = 1, x, y, opt; i <= m; ++i) {
        scanf("%d%d%d", &opt, &x, &y); Fk[i] = {opt, x, y, 0};
        if(opt == 1) {
            assert(x >= 1); assert(x <= n);
            assert(y >= 0); assert(y <= 1000000000);
            Fk[i].old = ar[x];
            bit_add(x, ar[x]);
            bit_add(x, y);
            ar[x] = y;
            vs.eb(y);
        }else {
            assert(x >= 1); assert(x <= y); assert(y <= n);
            assert(opt == 2);
            Fk[i].old = bit_query(y) ^ bit_query(x-1);
            vs.eb(Fk[i].old);
            //printf("- %d -\n", Fk[i].old);
        }
    }
    sort(all(vs));
    vs.erase(unique(all(vs)), vs.end());
    ALL = vs.size();
    //printf("--%d\n", ALL);
    int cntp = 0, cnta = 0;
    for(int i = 1; i <= n; ++i) {
        cw[++cntp].p = i;
        cw[cntp].ip = 1;
        cw[cntp].x = lower_bound(all(vs), br[i]) - vs.begin() + 1;
        cw[cntp].id = -1;
    }
    for(int i = 1, x, y, opt; i <= m; ++i) {
        opt = Fk[i].opt, x = Fk[i].x, y = Fk[i].y;
        if(opt == 1) {
            cw[++cntp].ip = opt;
            cw[cntp].p = x;
            cw[cntp].id = lower_bound(all(vs), Fk[i].old) - vs.begin() + 1;
            cw[cntp].x = lower_bound(all(vs), y) - vs.begin() + 1;
        }else {
            cw[++cntp].ip = opt;
            cw[cntp].p = x-1;
            cw[cntp].delta = -1;
            cw[cntp].x = lower_bound(all(vs), Fk[i].old) - vs.begin() + 1;
            cw[cntp].id = ++cnta;

            cw[++cntp].ip = opt;
            cw[cntp].p = y;
            cw[cntp].delta = 1;
            cw[cntp].x = cw[cntp-1].x;
            cw[cntp].id = cnta;
            QWE[cnta] = y-x+1;
        }
    }
    cdq(1, cntp);
    for(int i = 1; i <= cnta; ++i) printf("%d\n", QWE[i] - ANS[i]);
    return 0;
}

---

CSUSTOJ 1026：强制在线树套树

/**
 * Copyright (C), 2019-2019, csust
 * FileName: try
 * Author:   cwolf9
 * Date:     19-4-16 下午6:44
 * Description: ${DESCRIPTION}
 * History:
 * <author>          <time>          <version>          <desc>
 * Cwolf9           19-4-16           2019.1            ${DESCRIPTION}
 */

#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#define endl "\n"
#define fi first
#define se second
#define eb emplace_back
#define mk make_pair
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a),(b),sizeof((a)))
#define iis std::ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> pii;
typedef vector<int> VI;
typedef vector<pii> VPII;

const int MXN = 1e6 + 6;
const int MXE = 2e6 + 6;
const int INF = 0x3f3f3f3f;

int n, m;
struct lp {
    int l, r, sum;
}cw[54000007];
struct node {
    int opt, x, y, old;
}edge[MXE];
int ALL;
int ar[MXN], br[MXN];
int Root[MXN], NODE, yRoot[MXN];
int bit[MXN];
int lowbit(int x){return (x&(-x));}
void bit_Add(int x,int c){for(; x <= n; x += lowbit(x)) bit[x]^=c;}
int bit_Query(int x){int ANS = 0;for(; x; x -= lowbit(x)) ANS^=bit[x];return ANS;}

void update(int &cur, int x, int v, int l, int r) {
    if(!cur) {
        cur = ++ NODE;
        cw[cur].l = cw[cur].r = cw[cur].sum = 0;
    }
    cw[cur].sum += v;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(x <= mid) update(cw[cur].l, x, v, l, mid);
    else update(cw[cur].r, x, v, mid+1, r);
}
void update(int &cur, int old, int x, int l, int r, int p) {
    cur = ++ NODE;
    cw[cur] = cw[old];
    ++ cw[cur].sum;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(x <= mid) update(cw[cur].l, cw[old].l, x, l, mid, p);
    else update(cw[cur].r, cw[old].r, x, mid+1, r, p);
}
int Find(int l, int r, int aim, int rt) {
    if(l == r) return cw[rt].sum;
    int mid = (l + r) >> 1;
    if(aim <= mid) return Find(l, mid, aim, cw[rt].l);
    else return Find(mid+1, r, aim, cw[rt].r);
}
int query(int l, int r, int aim) {
    int ans = Find(1, ALL, aim, yRoot[r]) - Find(1, ALL, aim, yRoot[l]);
    for(; r; r -= lowbit(r)) ans += Find(1, ALL, aim, Root[r]);
    for(; l; l -= lowbit(l)) ans -= Find(1, ALL, aim, Root[l]);
    return ans;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("/home/cwolf9/CLionProjects/newOne/in.txt", "r", stdin);
    //freopen("/home/cwolf9/CLionProjects/newOne/out.txt", "w", stdout);
#endif
    scanf("%d%d", &n, &m);
    VI vs; vs.eb(-1); cw[0] = {0,0,0};
    for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]), vs.eb(ar[i]), bit_Add(i, ar[i]), br[i] = ar[i];
    for(int i = 1, opt, x, y; i <= m; ++i) {
        scanf("%d%d%d", &opt, &x, &y);
        edge[i] = {opt, x, y};
        if(opt == 1) {
            vs.eb(y);
        }
    }
    sort(all(vs));
    vs.erase(unique(all(vs)), vs.end());
    ALL = vs.size();
    for(int i = 1, tmp; i <= n; ++i) {
        tmp = lower_bound(all(vs), br[i]) - vs.begin();
        update(yRoot[i], yRoot[i-1], tmp, 1, ALL, 1);
        assert(tmp >= 1); assert(tmp <= ALL);
    }
    int aim = lower_bound(all(vs), 8) - vs.begin(), last = 0;
    //printf("---- %d\n", Find(1, ALL, aim, yRoot[6]) - Find(1, ALL, aim, yRoot[2]));
    for(int i = 1, opt, x, y; i <= m; ++i) {
        opt = edge[i].opt, x = edge[i].x, y = edge[i].y;
        if(opt == 1) {
            x = (x + last) % n + 1;
            int tmp1 = lower_bound(all(vs), ar[x]) - vs.begin();
            int tmp2 = lower_bound(all(vs), y) - vs.begin();
            assert(tmp1 >= 1); assert(tmp1 <= ALL);
            assert(tmp2 >= 1); assert(tmp2 <= ALL);
            bit_Add(x, ar[x]);
            bit_Add(x, y);
            ar[x] = y;
            while(x <= n) {
                update(Root[x], tmp1, -1, 1, ALL);
                update(Root[x], tmp2, 1, 1, ALL);
                x += lowbit(x);
            }
        }else {
            x = (x + last) % n + 1;
            y = (y + last) % n + 1;
            if(x > y) swap(x, y);
            int ans = bit_Query(y)^bit_Query(x-1);
            int tmp = lower_bound(all(vs), ans) - vs.begin();
            if(tmp == vs.size() || vs[tmp] != ans) {
                last = y - x + 1;
            }else {
                assert(tmp >= 1); assert(tmp <= ALL);
                last = (y - x + 1 - query(x - 1, y, tmp));
            }
            printf("%d\n", last);
        }
    }
    return 0;
}

整体二分

动态区间第k小

动态区间第k小的n种解法：here

洛谷P2617, ZOJ2112

练习题：洛谷P3332

就很板子的题。

整体二分类似于一些决策单调性的分治，可以解决诸多区间第\(k\)小的问题。

\(solve(l,r,L,R)\)表示当前值域为\([l,r]\)，当前操作为\([L,R]\)。

我们要对所有操作按照他们对应值域区间进行划分，并递归分治。分治层数只与值域区间相关，我们是带着和这个值域相关的询问向下分治。所以整体二分的复杂度也是很稳定的。

枚举\([L,R]\)：

• 如果当前操作是更新操作：若更新的值在\([l,mid]\)内，则用树状数组在当前更新操作所代表的序列下标位置\(+1\)，并将次操作归纳到下一层左区间内；反之归纳到下一层的右区间内。
• 如果当前操作是查询操作，树状数组询问区间\([cw[i].l,cw[i].r]\)内的值域情况，如果不小于\(cw[i].k\)就归入下一层左区间内；反之减去相应大小并归纳到下一层的右区间内。
• 终止条件：值域只有一个数，更新相应答案即可。

AC_Code:260ms

const int INF = 0x3f3f3f3f;
const int MXN = 2e5 + 7;
const int MXE = 1e6 + 7;
int n, m;
int bit[MXN];
void bit_add(int x,int c){for(;x <= n+1;x += lowbit(x)) bit[x]+=c;}
int bit_query(int x){int ans = 0;for(;x;x -= lowbit(x))ans+=bit[x];return ans;}
int ar[MXN];
struct lp {
    int l, r, v, id, ip;
}cw[MXN], cw1[MXN], cw2[MXN];
int ans[MXN];
int stk[MXN], top;
void solve(int l, int r, int L, int R) {
    if(l > r || L > R) return;
    if(l == r) {
        for(int i = L; i <= R; ++i) if(cw[i].ip == 2) ans[cw[i].id] = l;
        return;
    }
    int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
    top = 0;
    for(int i = L; i <= R; ++i) {
        if(cw[i].ip == 1) {
            if(cw[i].l <= mid) bit_add(cw[i].id, cw[i].v), cw1[++cnt1] = cw[i], stk[++top] = i;
            else cw2[++cnt2] = cw[i];
        }else {
            int k = bit_query(cw[i].r) - bit_query(cw[i].l - 1);
            if(k >= cw[i].v) cw1[++cnt1] = cw[i];
            else cw[i].v -= k, cw2[++cnt2] = cw[i];
        }
    }
    for(int i = 1; i <= top; ++i) bit_add(cw[stk[i]].id, -cw[stk[i]].v);
    for(int i = 1; i <= cnt1; ++i) cw[L + i - 1] = cw1[i];
    for(int i = 1; i <= cnt2; ++i) cw[L + cnt1 + i - 1] = cw2[i];
    solve(l, mid, L, L + cnt1 - 1);
    solve(mid + 1, r, L + cnt1, R);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("/home/cwolf9/CLionProjects/ccc/in.txt", "r", stdin);
//    freopen("/home/cwolf9/CLionProjects/ccc/out.txt", "w", stdout);
#endif
    int tim = read();
    while(tim --) {
        n = read(), m = read();
        int tot = 0, p = 0;
        for(int i = 1; i <= n; ++i) ar[i] = read(), cw[++ tot] = {ar[i], 0, 1, i, 1};
        char s[2];
        int l, r, k;
        for(int i = 1; i <= m; ++i) {
            scanf("%s", s);
            if (s[0] == 'Q') {
                l = read(), r = read(), k = read();
                cw[++tot] = {l, r, k, ++ p, 2};
            }else {
                l = read(), r = read();
                cw[++tot] = {ar[l], 0, -1, l, 1};
                cw[++tot] = {ar[l] = r, 0, 1, l, 1};
            }
        }
        solve(0, INF, 1, tot);
        for(int i = 1; i <= p; ++i) printf("%d\n", ans[i]);
    }
    return 0;
}

---

P3332 [ZJOI2013]K大数查询

坑点：会爆栈导致\(mle\)，\(mle\)是因为负数二分递归原因

mle的原因是负数分治递归下去的时候死循环了，就是(l,r)没变过

• solution1：如果现在操作里没有询问操作就break
• solution2：如果递归层数大于20层就break，因为死循环只出现在负数，只有插入会出现负数，可以肯定死循环的操作里没有循环操作
• solution3：既然负数会出问题，就把负数变成整数呗

这题和上面那题唯一的区别就是单点更新变成了区间更新，用一个可以区间加区间赋零的数据结构就行了。

可以树状数组也可以线段树（线段树就用两个lazy标记，一个区间加，一个区间赋值，注意区间赋值的lazy标记优先级比较高）

代码：1, 2

AC_Code

const int MXN = 1e5 + 7;
const int MXE = 1e6 + 7;
int n, m;
//sum[i] = sigma(ar[x])+(i+1)*sigma(delta[x])-sigma(x*delta[x])
//delta[]是差分数组
struct FenwickTree {
    static const int MAXN = 1e5 + 6;
    LL delta[MAXN], deltai[MAXN];
    void add1(int x, int v) {
        while (x <= n + 10) {
            delta[x] += v;
            x += lowbit(x);
        }
    }
    void add2(int x, int v) {
        while (x <= n + 10) {
            deltai[x] += v;
            x += lowbit(x);
        }
    }
    LL query1(int x) {
        LL sum = 0;
        while (x > 0) {
            sum += delta[x];
            x -= lowbit(x);
        }
        return sum;
    }
    LL query2(int x) {
        LL sum = 0;
        while (x > 0) {
            sum += deltai[x];
            x -= lowbit(x);
        }
        return sum;
    }
    void update(int l, int r, int x) {
        add1(l, x);
        add1(r + 1, -x);
        add2(l, l * x);
        add2(r + 1, -x * (r + 1));
    }
    LL range(int l, int r) {
        LL sum1 = l * query1(l - 1) - query2(l - 1);
        LL sum2 = (r + 1) * query1(r) - query2(r);
        return sum2 - sum1;
    }
}bit;
struct lp {
    int l, r;
    LL v;
    int id, ip;
    lp(){}
    lp(int _l, int _r, LL _v, int _id, int _ip) {
        l = _l, r = _r, v = _v, id = _id, ip = _ip;
    }
}cw[MXN], cw1[MXN], cw2[MXN];
int ans[MXN];
int stk[MXN], top;
void solve(int l, int r, int L, int R, int d) {
    if(d > 18) return;
    if(l > r || L > R) return;
    if(l == r) {
        for(int i = L; i <= R; ++i) if(cw[i].ip == 2) ans[cw[i].id] = l;
        return;
    }
    int mid = (l + r) / 2, cnt1 = 0, cnt2 = 0;
    top = 0;
    bool fl = false, fr = false;
    for(int i = L; i <= R; ++i) {
        if(cw[i].ip == 1) {
            if(cw[i].v > mid) bit.update(cw[i].l, cw[i].r, 1), cw1[++cnt1] = cw[i], stk[++top] = i;
            else cw2[++cnt2] = cw[i];
        }else {
            LL k = bit.range(cw[i].l, cw[i].r);
            if(k >= cw[i].v) cw1[++cnt1] = cw[i], fr = true;
            else cw[i].v -= k, cw2[++cnt2] = cw[i], fl = true;
        }
    }
    for(int i = 1; i <= top; ++i) bit.update(cw[stk[i]].l, cw[stk[i]].r, -1);
    for(int i = 1; i <= cnt2; ++i) cw[L + i - 1] = cw2[i];
    for(int i = 1; i <= cnt1; ++i) cw[L + cnt2 + i - 1] = cw1[i];
    if(fl) solve(l, mid, L, L + cnt2 - 1, d + 1);
    if(fr) solve(mid + 1, r, L + cnt2, R, d + 1);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("/home/cwolf9/CLionProjects/ccc/in.txt", "r", stdin);
//    freopen("/home/cwolf9/CLionProjects/ccc/out.txt", "w", stdout);
#endif
//    int tim = 1;
    n = read(), m = read();
    int p = 0;
    int l, r, opt;
    LL k;
    for(int i = 1; i <= m; ++i) {
        opt = read();
        if (opt == 1) {
            l = read(), r = read(), k = read();
            cw[i] = lp(l, r, k, l, 1);
        }else {
            l = read(), r = read(), k = read();
            cw[i] = lp(l, r, k, ++ p, 2);
        }
    }
    solve(-n, n, 1, m, 1);
    for(int i = 1; i <= p; ++i) printf("%d\n", ans[i]);
    return 0;
}