3110: [Zjoi2013]K大数查询
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 11654 Solved: 3505
[Submit][Status][Discuss]
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 Input
2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3
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
2
1
HINT
【样例说明】
第一个操作 后位置 1 的数只有 1 ， 位置 2 的数也只有 1 。 第二个操作 后位置 1
的数有 1 、 2 ，位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是
1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3
大的数是 1 。
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中c<=Maxlongint
题解
求第K大。
然后我们把权值设为n-c+1;
最后答案为n-ans+1就把问题转化为了第k小
不过这题是插入。其实不是很难毕竟只是把权值小于mid的数的位置都加一就行了，我们把修改二分和一个位置多少个权值没有关系。
和以前唯一的区别就是这次是整体修改，用线段树就行了（就是慢）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const long long N=;
struct query{
long long type,x,y,w,id;
}q[N],c2[N],c1[N];
long long ans[N],m,n,tot;
struct tree{
long long l,r,lazy,sum;
}tr[N*];
void update(long long now){
tr[now].sum=tr[now*].sum+tr[now*+].sum;
}
void pushdown(long long now){
if(tr[now].lazy==)return;
tr[now*].sum+=(tr[now*].r-tr[now*].l+)*tr[now].lazy;
tr[now*+].sum+=(tr[now*+].r-tr[now*+].l+)*tr[now].lazy;
tr[now*].lazy+=tr[now].lazy;
tr[now*+].lazy+=tr[now].lazy;
tr[now].lazy=;
}
void build(long long l,long long r,long long now){
tr[now].l=l;tr[now].r=r;
if(l==r)return;
long long mid=(l+r)>>;
build(l,mid,now*);
build(mid+,r,now*+);
}
void add(long long l,long long r,long long c,long long now){
pushdown(now);
if(tr[now].l==l&&tr[now].r==r){
tr[now].sum+=(tr[now].r-tr[now].l+)*c;
tr[now].lazy+=c;
return;
}
long long mid=(tr[now].l+tr[now].r)>>;
if(l>mid)add(l,r,c,now*+);
else if(r<=mid)add(l,r,c,now*);
else{
add(l,mid,c,now*);
add(mid+,r,c,now*+);
}
update(now);
}
long long check(long long l,long long r,long long now){
pushdown(now);
if(tr[now].l==l&&tr[now].r==r){
return tr[now].sum;
}
long long mid=(tr[now].l+tr[now].r)>>;
if(l>mid)return check(l,r,now*+);
else if(r<=mid)return check(l,r,now*);
else return check(l,mid,now*)+check(mid+,r,now*+);
}
void solve(long long l,long long r,long long L,long long R){
if(l>r)return ;
if(L==R){
for(long long i=l;i<=r;i++){
if(q[i].type==)ans[q[i].id]=L;
}
return;
}
long long mid=(L+R)>>;
long long lnow=;long long rnow=;
for(long long i=l;i<=r;i++){
if(q[i].type==){
if(q[i].w<=mid){
add(q[i].x,q[i].y,,);
c1[++lnow]=q[i];
}
else c2[++rnow]=q[i];
}
else{
long long tmp=check(q[i].x,q[i].y,);
if(tmp>=q[i].w)c1[++lnow]=q[i];
else{
q[i].w-=tmp;
c2[++rnow]=q[i];
}
}
}
for(long long i=;i<=lnow;i++){
if(c1[i].type==)add(c1[i].x,c1[i].y,-,);
}
for(long long i=;i<=lnow;i++){
q[l+i-]=c1[i];
}
for(long long i=;i<=rnow;i++){
q[l+lnow+i-]=c2[i];
}
solve(l,l+lnow-,L,mid);
solve(l+lnow,r,mid+,R);
}
int main(){
scanf("%lld%lld",&n,&m);
build(,n,);
for(long long i=;i<=m;i++){
long long k,a,b,c;
scanf("%lld%lld%lld%lld",&k,&a,&b,&c);
if(k==){
q[i].type=;q[i].x=a;q[i].y=b;q[i].w=n-c+;
}
else{
q[i].type=;q[i].x=a;q[i].y=b;q[i].w=c;q[i].id=++tot;
}
}
solve(,m,-n,n);
for(long long i=;i<=tot;i++){
printf("%lld\n",n-ans[i]+);
}
return ;
}