題意：

有兩種操作， 一個(gè)是插入一個(gè)[l,r]的區(qū)間，另一個(gè)是詢問一個(gè)區(qū)間[l,r]，前面有多少個(gè)區(qū)間完全包含了這個(gè)區(qū)間。

思路：

首先離散化。。

很容易想到的一個(gè)搞法是線段樹套平衡樹或者樹狀數(shù)組套平衡樹，也就是對(duì)于插入的區(qū)間，把[1,l]都插入一個(gè)r，然后對(duì)詢問的區(qū)間就是看[1,l]里面有多少個(gè)數(shù)>=r，然而這樣的空間復(fù)雜度是nlognlogn，n=50w明顯要跪了。。

然后就是對(duì)序列進(jìn)行分治。

對(duì)一個(gè)操作序列[a,b], 設(shè)m=(a+b)/2，先遞歸處理[a,m], [m+1,b]，然后考慮[a,m]里面的插入?yún)^(qū)間的操作對(duì)[m+1,b]里面詢問的影響。也就是轉(zhuǎn)化成靜態(tài)的問題。可以先把區(qū)間按照左端點(diǎn)排序，然后從左向右掃，掃到一個(gè)插入?yún)^(qū)間用樹狀數(shù)組就在r處+1，詢問就是答案加上sum(n)-sum(r-1)。

#include <iostream> #include <cstring> #include <string> #include <cstdio> #include <algorithm> #include <cmath> #include <cstdlib> #include <stack> #include <queue> #include <map> #include <vector> #include <cstdlib> using namespace std;#define LL long long #define N 500020 #define M 200200 #define eps 1e-8 #define MP make_pair #define Pi acos(-1.0) #pragma comment(linker, "/STACK:1024000000,1024000000") #define inf 0x3f3f3f3f #define ls (p[i].ch[0]) #define rs (p[i].ch[1]) #define Ls (i << 1) #define Rs (Ls | 1) #define md ((ll + rr) >> 1) #define lson ll, md, Ls #define rson md + 1, rr, Rsstruct node {int l, r, t, id;bool operator < (const node &b) const {return l < b.l;} }p[N], b[N]; int s[N*2];int san[N*2], cnt;int ans[N];int haxi(int x) {return lower_bound(san + 1, san + cnt + 1, x) - san; } void add(int x, int v) {while(x) {s[x] += v;x -= x & -x;} } int query(int x) {int ret = 0;while(x <= cnt) {ret += s[x];x += x & -x;}return ret; } void solve(int l, int r) {if(l >= r) return;int m = (l + r) / 2;solve(l, m);solve(m + 1, r);int c = 0;for(int i = l; i <= r; ++i)b[++c] = p[i];sort(b + 1, b + c + 1);for(int i = 1; i <= c; ++i) {int j = i;while(j <= c && b[j].l == b[i].l) ++j;--j;for(int k = i; k <= j; ++k) {if(b[k].t == 1 && b[k].id <= m) {add(b[k].r, 1);}}for(int k = i; k <= j; ++k) {if(b[k].t == 2 && b[k].id > m) {ans[b[k].id] += query(b[k].r);}}i = j;}for(int i = 1; i <= c; ++i) {if(b[i].t == 1 && b[i].id <= m)add(b[i].r, -1);} }int main() {//freopen("tt.txt", "r", stdin);int n;while(scanf("%d", &n) != EOF) {cnt = 0;for(int i = 1; i <= n; ++i){char op[4];int l, r;scanf("%s%d%d", op, &l, &r);if(op[0] == '+') p[i].t = 1;else p[i].t = 2;p[i].id = i;p[i].l = l, p[i].r = r;san[++cnt] = l;san[++cnt] = r;}memset(ans, 0, sizeof ans);memset(s, 0, sizeof s);sort(san + 1, san + cnt + 1);cnt = unique(san + 1, san + cnt + 1) - san - 1;for(int i = 1; i <= n; ++i)p[i].l = haxi(p[i].l), p[i].r = haxi(p[i].r);solve(1, n);for(int i = 1; i <= n; ++i)if(p[i].t == 2)printf("%d\n", ans[i]);return 0;}return 0; }

搜索

復(fù)制

總結(jié)

以上是生活随笔為你收集整理的UVALive 5871 Arnooks's Defensive Line (cdq分治)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。