【线段树套线段树】[ZJOI 2013] bzoj3110 K大数查询
题目点这里?整体二分题解点这里 被浙江的省选题真的搞得要疯了= = 那种又饿又冷又码不出代码的感觉简直是…………无!法!言!喻! 树套树本来是打算先放着之后再说的……orz现在看来是必须先攻破惹。。虽然估计换道题窝又不会了 = = 自己太弱要怎么办嘛。。。 然后想说 发现我的博客名取的还真是好 = = 。。。
Description有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。 Input第一行N,M 接下来M行,每行形如1 a b c或2 a b c Output输出每个询问的结果 Sample Input2 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 HINTN,M<=50000,N,M<=50000a<=b<=N 1操作中abs(c)<=N 2操作中abs(c)<=Maxlongint Code#include <cstdio> #include <iostream> #define lch (u << 1) #define rch (u << 1 | 1) using namespace std; int ReadInt() { int x = 0,sign = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') sign = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') {x = x*10 + ch-'0'; ch = getchar();} return x*sign; } const int maxn = 50000+5; const int maxm = 360 * maxn; int N,M; int root[3*maxn]; // 外层线段树 int sum[maxm],lazy[maxm],lc[maxm],rc[maxm]; // 内层线段树 int size; void insert(int u,int l,int r,int L,int R) { // 内层线段树 if(l == L && r == R) { sum[u] += r-l+1; lazy[u]++; return; } int mid = (l + r) >> 1; if(R <= mid) insert(lc[u] ? lc[u] : lc[u] = ++size,l,mid,L,R); else if(L > mid) insert(rc[u] ? rc[u] : rc[u] = ++size,mid+1,r,R); else { insert(lc[u] ? lc[u] : lc[u] = ++size,mid); insert(rc[u] ? rc[u] : rc[u] = ++size,R); } sum[u] += R - L + 1; } void add(int u,int R,int x) { // 外层线段树 insert(root[u] ? root[u] : root[u] = ++size,1,R); if(l == r) return; int mid = (l + r) >> 1; if(x <= mid) add(lch,R,x); else add(rch,x); } int count(int u,int R) { // 内层线段树 if(l == L && r == R) return sum[u]; int mid = (l + r) >> 1,ans = 0; if(R <= mid) ans = count(lc[u],R); else if(L > mid) ans = count(rc[u],R); else { ans += count(lc[u],mid); ans += count(rc[u],R); } ans += (R - L + 1) * lazy[u]; return ans; } int query(int u,int x) { // 外层线段树 if(l == r) return l; int mid = (l + r) >> 1; int cnt = count(root[rch],R); if(cnt >= x) return query(rch,x); else return query(lch,x - cnt); } int main() { N = ReadInt(); M = ReadInt(); int type,a,b,c; while(M--) { type = ReadInt(); a = ReadInt(); b = ReadInt(); c = ReadInt(); if(type == 1) add(1,c); else printf("%dn",query(1,c)); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |