題目鏈接：http://www.lydsy.com/JudgeOnline/problem.php?id=3110

Description

有N個(gè)位置，M個(gè)操作。操作有兩種，每次操作如果是1 a b c的形式表示在第a個(gè)位置到第b個(gè)位置，每個(gè)位置加入一個(gè)數(shù)c
如果是2 a b c形式，表示詢問從第a個(gè)位置到第b個(gè)位置，第C大的數(shù)是多少。

Input

第一行N，M
接下來M行，每行形如1 a b c或2 a b c

Output

輸出每個(gè)詢問的結(jié)果

題目大意：略。 思路：分治答案。答案范圍[-n, n]，從前往后掃描，若是插入操作且c>mid，則把線段樹中區(qū)間[a, b]加一，并置為為類別1；否則置為類別0。若是詢問操作，若目前線段樹中區(qū)間[a, b]的和小于等于c，則置為類別1；否則置為類別0，并把c減去區(qū)間[a, b]的和。然后分治處理，其中類別0中，答案范圍為[-n, mid]；類別1中，答案范圍為[mid + 1, n]。按類別排序后，兩個(gè)區(qū)間之間互不影響。時(shí)間復(fù)雜度為O(nlognlogn)。 代碼（4940MS）： 1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 typedef long long LL; 7 8 const int MAXN = 50010; 9 const int MAXT = MAXN << 2; 10 11 int sum[MAXT]; 12 int add[MAXT]; 13 bool clr[MAXT]; 14 15 #define ll (x << 1) 16 #define rr (ll | 1) 17 #define mid ((l + r) >> 1) 18 void initTree() { 19 sum[1] = add[1] = 0; 20 clr[1] = true; 21 } 22 23 void pushdown(int x, int l, int r) { 24 if(clr[x]) { 25 clr[ll] = clr[rr] = true; 26 sum[ll] = sum[rr] = add[ll] = add[rr] = 0; 27 clr[x] = false; 28 } 29 if(add[x]) { 30 sum[ll] += (mid - l + 1) * add[x]; 31 add[ll] += add[x]; 32 sum[rr] += (r - mid) * add[x]; 33 add[rr] += add[x]; 34 add[x] = 0; 35 } 36 } 37 38 void maintain(int x) { 39 sum[x] = sum[ll] + sum[rr]; 40 } 41 42 void modify(int x, int l, int r, int a, int b) { 43 if(a <= l && r <= b) { 44 add[x]++; 45 sum[x] += (r - l + 1); 46 } else { 47 pushdown(x, l, r); 48 if(a <= mid) modify(ll, l, mid, a, b); 49 if(mid < b) modify(rr, mid + 1, r, a, b); 50 maintain(x); 51 } 52 } 53 54 int query(int x, int l, int r, int a, int b) { 55 if(a <= l && r <= b) { 56 return sum[x]; 57 } else { 58 pushdown(x, l, r); 59 int res = 0; 60 if(a <= mid) res += query(ll, l, mid, a, b); 61 if(mid < b) res += query(rr, mid + 1, r, a, b); 62 return res; 63 } 64 } 65 #undef mid 66 67 struct Node { 68 int op, id, a, b, c, v; 69 void read(int i) { 70 id = i; 71 scanf("%d%d%d%d", &op, &a, &b, &c); 72 } 73 bool operator < (const Node &rhs) const { 74 if(v != rhs.v) return v < rhs.v; 75 return id < rhs.id; 76 } 77 } p[MAXN]; 78 int ans[MAXN]; 79 int n, m; 80 81 void work(int a, int b, int l, int r) { 82 if(l > r) return ; 83 if(a == b) { 84 for(int i = l; i <= r; ++i) 85 if(p[i].op == 2) ans[p[i].id] = a; 86 return ; 87 } 88 initTree(); 89 int mid = a + ((b - a) >> 1), t = l - 1; 90 for(int i = l; i <= r; ++i) { 91 if(p[i].op == 1) { 92 if(p[i].c > mid) modify(1, 1, n, p[i].a, p[i].b), p[i].v = 1; 93 else p[i].v = 0; 94 } else { 95 int s = query(1, 1, n, p[i].a, p[i].b); 96 if(p[i].c <= s) p[i].v = 1; 97 else p[i].v = 0, p[i].c -= s; 98 } 99 t += !p[i].v; 100 } 101 sort(p + l, p + r + 1); 102 work(a, mid, l, t); 103 work(mid + 1, b, t + 1, r); 104 } 105 106 int main() { 107 scanf("%d%d", &n, &m); 108 for(int i = 1; i <= m; ++i) p[i].read(i); 109 memset(ans + 1, 0x80, m * sizeof(int)); 110 work(-n, n, 1, m); 111 for(int i = 1; i <= m; ++i) 112 if(ans[i] >= -n) printf("%d\n", ans[i]); 113 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/oyking/p/3905850.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ K大数查询（分治）（Zjoi2013）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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