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

ACdream 1157 Segments (CDQ分治)

将修改操作和查询操作分开来，每次都用左区间的修改操作更新右区间的查询操作，因为左区间的修改操作对左区间的查询操作在递归左区间时就已经处理了，同理查询操作也是一样。

写的太暴力，还能过程能优化很多

#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 = 200050;
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) {}
    inline bool operator <(const mmp &b)const
    {
        if(r != b.r) return r > b.r;
        return l < b.l;
    }
    inline bool operator >(const mmp &b)const
    {
        return id < b.id;
    }
} q[N];
int ans[N], sum[N], cl[N], cr[N], mx;
int a[N];

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);
    for(int i = l; i <= r; i++)
    {
        if(q[i].id <= m && q[i].op) add(q[i].l, q[i].op);
        if(q[i].id > m && !q[i].op) ans[q[i].id] += getsum(q[i].l);
    }
    for(int i = l; i <= r; i++)
        if(q[i].id <= m && q[i].op) add(q[i].l, -q[i].op);
}

int main()
{
    int n;
    while(scan_d(n))
    {
        int l, r, cnt = 1, tot = 0;
        char op[5];
        for(int i = 1; i <= n; i++)
        {
            scanf("%s", op);
            if(op[0] == 'D')
            {
                scan_d(l), scan_d(r);
                cl[cnt] = l, cr[cnt++] = r;
                a[tot++] = l;
                a[tot++] = r;
                q[i] = {1, i, l, r};
            }
            else if(op[0] == 'Q')
            {
                scan_d(l), scan_d(r);
                a[tot++] = l;
                a[tot++] = r;
                q[i] = {0, i, l, r};
            }
            else
            {
                scan_d(l);
                q[i] = {-1, i, cl[l], cr[l]};
            }
        }
        sort(a, a + tot);
        mx = unique(a, a + tot) - a;
        for(int i = 1; i <= n; i++)
        {
            q[i].l = lower_bound(a, a + tot, q[i].l) - a + 1;
            q[i].r = lower_bound(a, a + tot, q[i].r) - a + 1;
        }
        fill(ans, ans + n + 1, 0);
        solve(1, n);
        sort(q + 1, q + n + 1, greater<mmp> ());
        for(int i = 1; i <= n; i++)
            if(!q[i].op) printf("%d\n", ans[i]);
    }
    return 0;
}