1. 首页
2. CDQ分治
3. 本页

UVALive 5871 Arnooks’s Defensive Line (CDQ分治)

在我们平常使用的分治中，每一个子问题只解决它本身（可以说是封闭的）。

而在cdq分治中，对于划分出来的两个子问题，前一个子问题用来解决后一个子问题而不是它本身。

具体算法流程如下：

1.将整个操作序列分为两个长度相等的部分（分）

2.递归处理前一部分的子问题（治1）

3.计算前一部分的子问题中的修改操作对后一部分子问题的影响（治2）

4.递归处理后一部分子问题（治3）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <class T> inline bool scan_d(T &ret) {char c; int sgn;if(c=getchar(),c==EOF) return 0;while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn;return 1;}
const int N = 500005;
struct mmp
{
    int op, id, l, r;
    mmp() {}
    mmp(int _op, int _id, int _l, int _r) : op(_op), id(_id), l(_l), r(_r) {}
} q[N];
int ans[N], sum[N << 1], mx;
vector<int> a;

inline bool cmp(const mmp &x, const mmp &y)
{
    if(x.r == y.r)
        return x.l < y.l;
    return x.r > y.r;
}

void add(int x, int val)
{
    for(int i = x; i <= mx; i += i & (-i)) sum[i] += val;
}
int getsum(int x, int res = 0)
{
    for(int i = x; i > 0; i -= i & (-i)) res += sum[i];
    return res;
}
void solve(int l, int r)
{
    if(l == r) return;
    int m = (l + r) >> 1;
    solve(l, m);
    solve(m + 1, r);
    sort(q + l, q + r + 1, cmp);
    for(int i = l; i <= r; i++)
    {
        if(q[i].id <= m) {
            if(q[i].op) add(q[i].l, 1);
        }
        else {
            if(q[i].op == 0)
                ans[q[i].id] += getsum(q[i].l);
        }
    }
    for(int i = l; i <= r; i++)
        if(q[i].id <= m) {
            if(q[i].op) add(q[i].l, -1);
        }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin >> n)
    {
        char op;
        cin.ignore();
        a.clear();
        int l, r;
        for(int i = 1; i <= n; i++)
        {
            cin >> op >> l >> r;
            if(op == '+') q[i] = {1, i, l, r};
            else q[i] = {0, i, l, r};
            a.push_back(l);
            a.push_back(r);
        }
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
        for(int i = 1; i <= n; i++)
        {
            q[i].l = int(lower_bound(a.begin(), a.end(), q[i].l) - a.begin()) + 1;
            q[i].r = int(lower_bound(a.begin(), a.end(), q[i].r) - a.begin()) + 1;
        }
        fill(ans, ans + n + 1, 0);
        mx = (int)a.size();
        solve(1, n);
        sort(q + 1, q + n + 1, [] (const mmp &x, const mmp &y) { return x.id < y.id; });
        for(int i = 1; i <= n; i++)
            if(!q[i].op) cout << ans[i] << "\n";
    }
    return 0;
}

/*
9
+ 5 10
+ 7 20
+ 3 15
? 9 12
+ 10 20
? 8 9
+ 6 30
? 8 9
? 9 12

*/