有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c
如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。
[BZOJ]3110 [ZJOI2013] K大数查询 整体二分
3110: [Zjoi2013]K大数查询Time Limit:?20 Sec?? Memory Limit:?512 MBSubmit:?10240?? Solved:?3053 [ Submit][ Status][ Discuss] DescriptionInput第一行N,M
接下来M行,每行形如1 a b c或2 a b c Output输出每个询问的结果
Sample Input
2 5
1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3 Sample Output1
2 1 HINT
N,M<=50000,N,M<=50000 SourceHOME?Back 发现整体二分居然如此好用?? 本来以为要树套树的没想到整体二分再用个树状数组就可以了... 好写好调啊. 答案显然具有二分性, 于是我们考虑尝试一波整体二分. 我们对答案进行二分,每次判断一个询问的区间比当前二分的值小的数目和该询问的k作比较来判断二分大了还是二分小了. 而修改操作相当于就是区间加减... 这个用线段树可以维护. 然后就是普通的整体二分辣. 从别人博客里发现这道题有负数的情况可以n - c + 1来扩展成1~2n+1的值域. 然后第k大就变成第k小了, 妙哇妙哇. 只需要在输出的时候再减回来就可以了. 而且树状数组只需要再维护一个差分数组就可以资瓷区间加区间查询?? 新技能get. #include<bits/stdc++.h> using namespace std; typedef long long lnt; const int maxn = 1e5 + 5; bool vis[maxn]; lnt c[2][maxn]; int n,m,tot,lim,ans[maxn]; inline const int read() { register int x = 0,f = 1; register char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();} while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0',ch = getchar(); return f * x; } struct point { int x,y,k,id,opt; }a[maxn],tmp[maxn]; inline void mdy(int k,int x,int val) { for (; x <= lim; x += x & -x) c[k][x] += val; } inline void modify(int x,int y,int f) { mdy(0,x,f),mdy(1,f * (x - 1)),mdy(0,y + 1,-f),-f * y); } inline lnt qry(int k,int x) { lnt tmp = 0; for (; x; x -= x & -x) tmp += c[k][x]; return tmp; } inline lnt query(int x,int y) { return qry(0,y) * y - qry(1,y) - qry(0,x - 1) * (x - 1) + qry(1,x - 1); } void solve(int lf,int rg,int L,int R) { register int i; if (L == R) { for (i = lf; i <= rg; ++ i) if (a[i].opt) ans[a[i].id] = L; return; } lnt sum = 0; int mid = (L + R) >> 1,cnt = 0; for (i = lf; i <= rg; ++ i) { if (a[i].opt) { sum = query(a[i].x,a[i].y); if (sum < a[i].k) vis[i] = false,a[i].k -= (int)sum; else vis[i] = true,++ cnt; } else if (a[i].k <= mid){ modify(a[i].x,a[i].y,+1),vis[i] = true; cnt ++; } else vis[i] = false; } for (i = lf; i <= rg; ++ i) if (!a[i].opt && a[i].k <= mid) modify(a[i].x,-1); int l1 = lf,l2 = lf + cnt; for (i = lf; i <= rg; ++ i) (vis[i]) ? tmp[l1 ++] = a[i] : tmp[l2 ++] = a[i]; for (i = lf; i <= rg; ++ i) a[i] = tmp[i]; solve(lf,l1 - 1,L,mid),solve(l1,l2 - 1,mid + 1,R); } int main() { n = read(),m = read(); register int i; for (i = 1; i <= m; ++ i) { a[i].opt = read() - 1,a[i].x = read(),a[i].y = read(),a[i].k = read(); if (a[i].opt) a[i].id = ++ tot; else a[i].k = n - a[i].k + 1,lim = max(lim,a[i].k); } solve(1,1,lim); for (i = 1; i <= tot; ++ i) printf("%dn",n - ans[i] + 1); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |