3110: [Zjoi2013]K大数查询 线段树套线段树 标记永久化
发布时间:2020-12-14 02:02:51 所属栏目:大数据 来源:网络整理
导读:外层权值线段树,内层区间线段树。 每次给一个区间 [ l , r ] 增加一个数 x ,我们就把权值线段树中区间包含 x 的节点的区间线段树上与 [ l , r ] 有关的节点加上这个节点代表的区间的长度。(卧槽好长的一句话慢慢理解。。。) 然后每次查询时类似二分答案
外层权值线段树,内层区间线段树。 #include<iostream>
#include<cstdio>
#include<queue>
#include<set>
#include<map>
#include<algorithm>
#define ll long long
#define N 200005
#define M 7000005
using namespace std;
int tree[M][2],sum[M],tag[M];
int root[N],n,m,cnt;
inline int read()
{
int a=0,f=1; char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
return a*f;
}
void add(int &k,int x,int y,int l,int r)
{
if (!k) k=++cnt;
sum[k]+=r-l+1;
if (l==x&&r==y) {tag[k]++; return;}
int mid=x+y>>1;
if (r<=mid) add(tree[k][0],x,mid,l,r);
else if (l>mid) add(tree[k][1],mid+1,y,r);
else add(tree[k][0],mid),add(tree[k][1],r);
}
void insert(int k,int r,int val)
{
add(root[k],1,r);
if (x==y) return;
int mid=x+y>>1;
if (val<=mid) insert(k<<1,r,val);
else insert(k<<1|1,val);
}
int ask(int k,int a)
{
if (l==x&&r==y) return sum[k]+a*(r-l+1);
int mid=x+y>>1;
if (r<=mid) return ask(tree[k][0],a+tag[k]);
else if (l>mid) return ask(tree[k][1],a+tag[k]);
else return ask(tree[k][0],a+tag[k])+ask(tree[k][1],a+tag[k]);
}
inline int query(int x,int rank)
{
int k=1,l=1,r=n;
while (l!=r)
{
int mid=l+r>>1;
int sum=ask(root[k<<1|1],0);
if (rank<=sum) k=k<<1|1,l=mid+1;
else k=k<<1,r=mid,rank-=sum;
}
return l;
}
int main()
{
n=read(); m=read();
for (int i=1;i<=m;i++)
{
int opt=read(),l=read(),r=read(),k=read();
if (opt==1) insert(1,k);
else printf("%dn",query(l,k));
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |