首页 > 代码库 > bzoj 3110

bzoj 3110

2024-08-05 19:24:23   220人阅读

题意：戳这里

思路：可以用cdq分治（很明显这种模型妹纸分治法很解决）。。不过为了学习树套树特地写了一下。。

        所谓的树套树也第一层(最外层)普通的维护的是一个node,而树套树维护的是一个数据结构（一棵树）。。

        树套树一般可以解决2维模型。。1维的话也就是普通的数据结构了。

        比如poi07 的mokia其实就是一个2为线段树，不够空间不够所以必须写成树套树。。

        本题的话如把权值看成一维，本来位置看成1维，那么其实也是2维模型。

        插入就等价于每次在一条x=c 横线的[a,b]之间每个位置都插入1遍

        查询等价于求第k大的在哪条横线上。。   

        对于这一题的话，可以如下：

              首先最外层维护的是权值构成的线段树，

              而对于每个权值，又对应着一棵线段树，不过这个线段树是下标线段树

              由于空间有限，所以有用到才动态分配内存。。

              然后每次插入的话在最外层包括value=http://www.mamicode.com/c的logn段里面都插入，

              查询的每次二分，左边太小右边找，正好从外层线段树从上到下。。

              时间复杂度O(mlog2n)

       

code：

 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #include<string> 8 #include<map> 9 #include<set>10 #include<vector>11 #include<queue>12 #include<stack>13 #define M0(x)  memset(x, 0, sizeof(x))14 using namespace std;15 #define lson lc[rt], l, m16 #define rson rc[rt], m+1, r17 const int N = 51000, M = 15000000;18 int rt[N<<2], sum[M], lc[M], rc[M], lz[M];19 int n, m, L, R, cnt, c;20 21 inline void push_up(const int& rt){22      sum[rt] = sum[lc[rt]] + sum[rc[rt]];23 }24 25 inline void push_down(const int &rt, const int& l, const int &r){26     if (lz[rt]){27           if (!lc[rt]) lc[rt] = ++cnt;28           if (!rc[rt]) rc[rt] = ++cnt;29           sum[lc[rt]] += lz[rt] * ((r-l+2)>>1), sum[rc[rt]] += lz[rt] * ((r-l+1)>>1);30           lz[lc[rt]] += lz[rt], lz[rc[rt]] += lz[rt];31           lz[rt] = 0;             32     }   33 }34 35 int query(const int& rt,const int& l, const int& r){36     if (!rt) return 0;37     if (L <= l && r <= R) return sum[rt];38     int m = (l + r) >> 1, tmp1 = 0, tmp2 = 0;39     push_down(rt, l, r);40     if (L <= m) tmp1 = query(lson);41     if (R > m) tmp2 = query(rson);42     return tmp1 + tmp2 + (min(R, r) - max(l, L) + 1) * lz[rt];43 }44 45 int query(int k){46     int l = 1, r = n, mid, cur = 1, tmp;47     while (l <= r){48           if (l == r) return l;49           mid = (l + r) >> 1;50           tmp = query(rt[cur<<1], 1, n);51           if (tmp >= k) r = mid, cur <<= 1;52           else l = mid + 1, k -= tmp, cur = cur<<1|1;  53     }54     return l;55 }56 57 void update(int &rt,const int& l,const int& r){58      if (!rt) rt = ++cnt;59      if (L <= l && r <= R){60            sum[rt] += (r - l + 1), ++lz[rt];61            return;      62      }63      int m = (l + r) >> 1;64      push_down(rt, l, r);65      if (L <= m) update(lson);66      if (R > m) update(rson);67      push_up(rt);68 }69 70 void insert(const int& c){71      int l = 1, r = n, cur = 1, mid;72      while (l <= r){73          update(rt[cur], 1, n);74          if (l == r) break;75          mid = (l + r) >> 1;76          if (c <= mid) cur<<= 1, r = mid;77          else l = mid + 1, cur = cur<<1|1;78      }    79 }80 81 void solve(){82      cnt = 0;83      int op;  84      while (m--){85            scanf("%d%d%d%d", &op, &L, &R, &c);86            if (op==1) c = n - c + 1, insert(c);87            else printf("%d\n", n - query(c) + 1);88      }     89 }90 91 int main(){92     freopen("a.in", "r", stdin);93     freopen("a.out", "w", stdout);94     while (scanf("%d%d", &n, &m) != EOF){95           solve();96     }97     return 0;98 }
View Code

code

 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #include<string> 8 #include<map> 9 #include<set>10 #include<vector>11 #include<queue>12 #include<stack>13 #define M0(x)  memset(x, 0, sizeof(x))14 using namespace std;15 #define lson lc[rt], l, m16 #define rson rc[rt], m+1, r17 const int N = 50100, M = 15000000;18 int rt[N<<2], sum[M], lc[M], rc[M], lz[M];19 int n, m, L, R, cnt, c;20 21 int query(const int& rt,const int& l, const int& r){22     if (!rt) return 0;23     if (L <= l && r <= R) return sum[rt];24     int m = (l + r) >> 1, tmp1 = 0, tmp2 = 0;25     if (L <= m) tmp1 = query(lson);26     if (R > m) tmp2 = query(rson);27     return tmp1 + tmp2 + (min(R, r) - max(l, L) + 1) * lz[rt];28 }29 30 int query(int k){31     int l = 1, r = n, mid, cur = 1, tmp;32     while (l <= r){33           if (l == r) return l;34           mid = (l + r) >> 1, tmp = query(rt[cur<<1], 1, n);35           if (tmp >= k) r = mid, cur <<= 1;36           else l = mid + 1, k -= tmp, cur = cur<<1|1;  37     }38     return l;39 }40 41 void update(int &rt,const int& l,const int& r){42      if (!rt) rt = ++cnt;43      if (L <= l && r <= R){44            sum[rt] += (r - l + 1), ++lz[rt];45            return;      46      }47      int m = (l + r) >> 1;48      if (L <= m) update(lson);49      if (R > m) update(rson);50      sum[rt] = sum[lc[rt]] + sum[rc[rt]] + lz[rt] * (r - l + 1);51 }52 53 void insert(const int& c){54      int l = 1, r = n, cur = 1, mid;55      while (l <= r){56          update(rt[cur], 1, n);57          if (l == r) break;58          mid = (l + r) >> 1;59          if (c <= mid) cur<<= 1, r = mid;60          else l = mid + 1, cur = cur<<1|1;61      }    62 }63 64 void solve(){65      cnt = 0;66      int op;  67      while (m--){68            scanf("%d%d%d%d", &op, &L, &R, &c);69            if (op==1) c = n - c + 1, insert(c);70            else printf("%d\n", n - query(c) + 1);71      }     72 }73 74 int main(){75     freopen("a.in", "r", stdin);76     freopen("a.out", "w", stdout);77     while (scanf("%d%d", &n, &m) != EOF){78           solve();79     }80     return 0;81 }
View Code

第一个lazy直接下放慢成狗。。学习了一下优美姿势快了不少。。

              

 

 

 

        

      

bzoj 3110


联系
我们