有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c
如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。
bzoj3110 K大数查询
发布时间:2020-12-14 02:04:18 所属栏目:大数据 来源:网络整理
导读: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 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 HINT
N,M<=50000,N,M<=50000 2操作中abs(c)<=Maxlongint 一道树套树的题 外层是一颗权值线段树 内层是传统的区间线段树 插入:在a-b插入权值c? 在外层线段树所有包含权值c的线段中,在其里层的线段树插入线段a-b 询问:在a-b中询问第k大的权值 从外层线段树(权值)开始,如果右孩子的内层线段树在区间a-b中的计数超过k个,显然答案在右孩子,否则在左孩子,以此类推 代码: </pre><pre name="code" class="cpp">#include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> using namespace std; struct Tree { int l,r,lazy,sum; }t[20000010]; int root[200010]; int n,m,sz,a,b,c; inline int ReadInt();//输入优化 void push_down(int k,int l,int r); int query(int k,int r,int a,int b); void modify(int &k,int b); void insert(); int solve(); int main() { n = ReadInt(); m = ReadInt(); for(int Z = 1; Z <= m; Z ++) { int f = ReadInt(); a = ReadInt(); b = ReadInt(); c = ReadInt(); if(f == 1) { c = n - c + 1; insert(); } else printf("%dn",n - solve() + 1); } return 0; } inline int ReadInt() { int x = 0,f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f =- 1; ch=getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } void push_down(int k,int r) { if(!t[k].lazy || l == r) return; if(!t[k].l) sz ++,t[k].l = sz; if(!t[k].r) sz ++,t[k].r = sz; t[ t[k].l ].lazy += t[k].lazy; t[ t[k].r ].lazy += t[k].lazy; int mid = (l + r) >> 1; t[ t[k].l ].sum = (mid - l + 1) * t[k].lazy; t[ t[k].r ].sum = (r - mid) * t[k].lazy; t[k].lazy = 0; } int query(int k,int b) { if(!k) return 0; push_down(k,l,r); if(l == a && r == b) return t[k].sum; int mid = (l + r) >> 1; if(b <= mid) return query(t[k].l,mid,b); else if(a > mid) return query(t[k].r,mid + 1,b); else return query(t[k].l,mid) + query(t[k].r,b); } void modify(int &k,int b) { if(!k) sz ++,k = sz; push_down(k,r); if(l == a && r == b) { t[k].sum += r - l + 1; t[k].lazy ++; return; } int mid = (l + r) >> 1; if(b <= mid) modify(t[k].l,b); else if(a > mid) modify(t[k].r,b); else { modify(t[k].l,mid); modify(t[k].r,b); } t[k].sum = t[ t[k].l ].sum + t[ t[k].r ].sum; } void insert() { int k = 1,l = 1,r = n; while(l != r) { int mid = (l + r) >> 1; modify(root[k],1,n,b); if(c <= mid) r = mid,k = k << 1; else l = mid + 1,k = k << 1|1; } modify(root[k],b); } int solve() { int k = 1,r = n; while(l != r) { int mid = (l + r) >> 1; int t = query(root[k << 1],b); if(t >= c) r = mid,k <<= 1; else l = mid + 1,k = k << 1|1,c -= t; } return l; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |