有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c
如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。
3110: [Zjoi2013]K大数查询
发布时间:2020-12-14 02:19:08 所属栏目:大数据 来源:网络整理
导读: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
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 Output
1
2 1 思路:线段树套线段树,外层线段树表示权值,内层线段树维护出现的位置及次数 PS:空间动态开。这里懒惰标记可以不PushDown,感觉PushDown会访问一些本来可以不访问也就是不用开辟的节点,省空间。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define maxn 50080 #define maxm 30058000 int root[maxn<<2]; int sum[maxm],lazy[maxm],lson[maxm],rson[maxm]; int n,m,cnt; void scanf_f(int & x) { x = 0; char c = getchar(); while(!(c >= '0' && c <= '9')) c = getchar(); while(c >= '0' && c <= '9') { x = x*10 + c - '0'; c = getchar(); } } /* void PushDown(int node,int l,int r) { if(lazy[node]) { int mid = (l+r) >> 1; if(lson[node] == 0) lson[node] = ++cnt; if(rson[node] == 0) rson[node] = ++cnt; sum[lson[node]] += lazy[node]*(mid-l+1); lazy[lson[node]] += lazy[node]; sum[rson[node]] += lazy[node]*(r-mid); lazy[rson[node]] += lazy[node]; } lazy[node] = 0; } */ void PushUp(int node,int r) { sum[node] = sum[lson[node]] + sum[rson[node]] + lazy[node]*(r-l+1); } void add(int & node,int L,int R,int r) { if(!node) node = ++cnt; if(L == l && R == r) { sum[node] += r-l+1; lazy[node]++; return; } //PushDown(node,L,R); int mid = (L+R) >> 1; if(r <= mid) add(lson[node],mid,l,r); else if(l > mid) add(rson[node],mid+1,R,r); else add(lson[node],mid),add(rson[node],r); PushUp(node,R); } void Add(int l,int r,int k) { int node = 1; int L = 1,R = n; while(L < R) { int mid = (L+R) >> 1; add(root[node],1,n,r); if(k > mid) { node = node << 1 | 1; L = mid+1; } else { node = node << 1; R = mid; } } add(root[node],r); } int query(int node,int r) { if(!node) return 0; if(L == l && R == r) return sum[node]; //PushDown(node,R); int ans = lazy[node]*(r-l+1); int mid = (L+R) >> 1; if(mid >= r) return query(lson[node],r)+ans; else if(mid < l) return query(rson[node],r)+ans; else return query(lson[node],mid) + query(rson[node],r) + ans; } int Query(int l,R = n; while(L < R) { int mid = (L+R) >> 1; int temp = query(root[node<<1|1],r); if(temp >= k) { L = mid+1; node = node << 1 | 1; } else { R = mid; node = node << 1; k -= temp; } } return L; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d%d",&n,&m); for(int i = 1;i <= m;i++) { int opt,r,c; //scanf("%d%d%d%d",&opt,&l,&r,&c); scanf_f(opt); scanf_f(l); scanf_f(r); scanf_f(c); if(opt == 1) { Add(l,c); } else { printf("%dn",Query(l,c)); } } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |