3723 -- 【ZJOI2013】K大数查询
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
对于每个询问回答k 大数是多少。
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
【样例说明】
第一个操作后位置1 的数只有1，位置2 的数也只有1。
第二个操作后位置1的数有1、2，位置2 的数也有1、2。
第三次询问位置1 到位置1 第2 大的数是1。
第四次询问位置1 到位置1 第1 大的数是2。第五次询问位置1 到位置2 第3大的数是1。
Hint
【数据规模与约定】
30%的数据n=m=1000
100%的数据n,m≤50000，并且后7 个点的数据n，m 的范围从32000 到50000
近似成等差数列递增。a≤b≤n,1 操作中|c|≤n,2 操作中|c|≤maxlongint
线段树套线段树，外部线段树记录第k大（数据没有负数），内部线段树是维护标记的区间线段树，表示这里面几个数..
插入c的时候转换为第k大（c=n-c+1）,然后用类似二分的方法找c，输出的时候换为n-solve()+1
#include<iostream>
#include<cstdio>
#include<cstring>
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define q 200005
#define w 20000005
using namespace std;
int root[q]={0},ct=0,n,m;
int a,b,c;
struct Segtree
{
int l,r,sum,lazy;
}tree[w];
void Pushdown(int x,int l,int r)
{
if(tree[x].lazy==0||l==r)return;
if(tree[x].l==0)tree[x].l=++ct;
if(tree[x].r==0)tree[x].r=++ct;
int mid=(l+r)>>1;
tree[tree[x].l].lazy+=tree[x].lazy;
tree[tree[x].r].lazy+=tree[x].lazy;
tree[tree[x].l].sum+=tree[x].lazy*(mid-l+1);
tree[tree[x].r].sum+=tree[x].lazy*(r-mid);
tree[x].lazy=0;
}
void Pushup(int x)
{
tree[x].sum=tree[tree[x].l].sum+tree[tree[x].r].sum;
}
void change(int &root,int r,int a,int b)
{
if(root==0){root=++ct;}//
Pushdown(root,l,r);
if(l==a&&r==b)
{
tree[root].sum+=r-l+1;
tree[root].lazy++;
return;
}
int mid=(l+r)>>1;
// if(a<=mid)change(tree[root].l,mid,a,b);
// if(r>mid)change(tree[root].r,mid+1,b);
if(b<=mid)change(tree[root].l,b);
else if(a>mid)change(tree[root].r,b);
else
{
change(tree[root].l,mid);
change(tree[root].r,b);
}
Pushup(root);
}
void MDF()
{
int o=1,l=1,r=n;
while(l!=r)
{
int mid=(l+r)>>1;
change(root[o],1,b);
if(c<=mid){o=L(o);r=mid;}
else {o=R(o);l=mid+1;}
}
change(root[o],b);
}
int get(int root,int b)
{
if(root==0)return 0;
Pushdown(root,r);
if(l==a&&r==b)return tree[root].sum;
int mid=(l+r)>>1;
if(b<=mid)return get(tree[root].l,b);
else if(a>mid)return get(tree[root].r,b);
else
{
return get(tree[root].l,mid)+get(tree[root].r,b);
}
}
int Get()
{
int o=1,r=n;
while(l!=r)
{
int mid=(l+r)>>1;
int t=get(root[L(o)],b);
// cout<<"**"<<t<<endl;
if(c<=t){r=mid;o=L(o);}
else {l=mid+1;o=R(o);c-=t;}
}
return l;
}
int main()
{
// freopen("sequence1.in","r",stdin);
// freopen("sequence1.out","w",stdout);
int cmd;
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d%d%d",&cmd,&a,&b,&c);
if(cmd==1)
{
c=n-c+1;
MDF();
}
else printf("%dn",n-Get()+1);
}
return 0;
}
