【整体二分】[ZJOI 2013] bzoj3110 K大数查询
题目点这里 树套树题解点这里 调完这个。。一晚上居然就又过去了。。。TAT 先说下效率 我的树套树是283136 kb?7556 ms(永久化标记的)分治是3148 kb?1296 ms _(:з)∠)_代码长度的话。。两个都差不多T_____T 思路: 整体二分这玩意。。和cdq分治挺像的样子。。 从我的理解来说。。。cdq分治是用[l,mid]更新[mid + 1,r] 根据[l,mid]来把询问划分给[l,mid]或者[mid + 1,r]
注意到条件 abs(c) <= N 那么我们可以按照权值来做 定义solve(S,l,r)表示处理集合S的操作 其中S中的更新操作add(c)的 c ∈ [l,r] 询问操作的答案 ans ∈ [l,r] 并且保证S中所有的操作编号是上升序列 那么我们要求的就是solve(1...M,-N,N) (in fact..数据没有负数.....所以写1,N也是一样的。。) 处理当前solve 首先二分出mid = (l + r) >> 1 然后对于更新操作 很明显如果c <= mid那么它要被划分到左边 其他要划分在右边 对于询问 首先要明确!!第k大的意思!不是从小到大第k个!!!!是从大到小!!!(我就被这里坑哭了 = =) 所以很明显我们要统计的是此时右边区域会有多少数 如果 cnt < k 那么答案应该是在左边(记得k -= cnt) 反之在右边 统计cnt的方法是这样的 我们对于右边区域直接在一维树状数组上模拟操作 由于集合S的顺序是有序的 那么操作次序就可以得到保证 一维树状数组的区间更新区间查询の方法点这里 注意每次模拟完树状数组是要清空的 但是为了节省时间我们直接记录一个操作时间就行了 然后我们把当前S划分成了左右两个集合S1 S2以后 递归下去即可 = v = S为空的时候直接返回 最后の边界就是l == r的时候 可以直接更新ans了! 神坑:这!题!不!能!用!cin!和!cout!!!!!本来写的是取消同步的输入输出流 一直RE TAT #include "cstdio" #define lowbit(x) (x & (-x)) using namespace std; const int Nmax = 50005; int N,M; struct Option{ int sign,x,y,c; }op[Nmax]; int tot = -1,ans[Nmax]; int q[Nmax],tmp[2][Nmax]; namespace BIT{ int t[Nmax][2],d[Nmax][2]; void update(bool s,int pos,int c) { for (int i = pos; i <= N; i += lowbit(i)) { if (t[i][s] != tot) { t[i][s] = tot; d[i][s] = 0; } d[i][s] += c; } } int get_sum(bool s,int pos) { int res = 0; for (int i = pos; i; i -= lowbit(i)) { if (t[i][s] != tot) { t[i][s] = tot; d[i][s] = 0; } res += d[i][s]; } return res; } void Add(int x,int y) { update(0,1); update(0,y + 1,-1); update(1,x); update(1,-(y + 1)); } int Query(int x,int y) { int temp = get_sum(0,y) * (y + 1) - get_sum(1,y); temp -= get_sum(0,x - 1) * x - get_sum(1,x - 1); return temp; } } void solve(int L,int R,int l,int r) { if (L > R) return; ++tot; int mid = (l + r) >> 1; if (l == r) { for (int i = L; i <= R; ++i) if (op[q[i]].sign == 2) ans[q[i]] = mid; return; } tmp[0][0] = tmp[1][0] = 0; using namespace BIT; for (int i = L; i <= R; ++i) { int temp = q[i]; if (op[temp].sign == 1) { if (op[temp].c <= mid) tmp[0][++tmp[0][0]] = temp; else { tmp[1][++tmp[1][0]] = temp; Add(op[temp].x,op[temp].y); } } else { int cnt = Query(op[temp].x,op[temp].y); if (cnt < op[temp].c) { op[temp].c -= cnt; tmp[0][++tmp[0][0]] = temp; } else tmp[1][++tmp[1][0]] = temp; } } int tl = L,t2 = L + tmp[0][0] - 1; for (int i = 1; i <= tmp[0][0]; ++i) q[tl++] = tmp[0][i]; for (int i = 1; i <= tmp[1][0]; ++i) q[tl++] = tmp[1][i]; solve(L,t2,mid); solve(t2 + 1,R,mid + 1,r); } int main() { scanf("%d%d",&N,&M); for (int i = 1; i <= M; ++i) { scanf("%d%d%d%d",&op[i].sign,&op[i].x,&op[i].y,&op[i].c); q[i] = i; } solve(1,M,1,N); for (int i = 1; i <= M; ++i) { if (op[i].sign == 2) printf("%dn",ans[i]); } return 0; } 哦对了。。其实这题不用写树状数组。。STL暴力就可以过 。。。 来自:http://blog.csdn.net/qq_21110267/article/details/44514709 #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int maxn = 50000 + 10; struct opt { int i,k,a,b,c; bool operator < (const opt& rhs) const { if(c == rhs.c) return i < rhs.i; return c > rhs.c; } }A[maxn]; vector<opt> T; int ID[maxn]; bool ins[maxn]; int main() { int n,m; scanf("%d %d",&n,&m); for(int i = 1; i <= m; i++) { int k,c; scanf("%d %d %d %d",&k,&a,&b,&c); A[i] = (opt){i,c}; if(k == 1) T.push_back(A[i]); } sort(T.begin(),T.end()); for(int i = 0; i < T.size(); i++) ID[T[i].i] = i; for(int i = 1; i <= m; i++) if(A[i].k == 1) ins[ID[i]] = 1; else { int j,c = 0; for(j = 0; j < T.size(); j++) if(ins[j]) { int len = min(A[i].b,T[j].b) - max(A[i].a,T[j].a) + 1; if(len <= 0) continue; if((c += len) >= A[i].c) break; } printf("%dn",T[j].c); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |