bzoj3110 [Zjoi2013]K大数查询（整体二分+线段树）

bzoj3110 [Zjoi2013]K大数查询

原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=3110

题意：
有N个位置，M个操作。
操作有两种，：
1 a b c的形式，表示在第a个位置到第b个位置，每个位置加入一个数c。
2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

数据范围
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中c<=Maxlongint

题解：
首先有三个东西：时间，值域，区间。
值域和区间是比较难处理的，原始的方法就是值域线段树套个位置线段树。
在这种处理方法中，实际上是二分了值域，然后处理区间。
这里二分值域也有把二分中线的左边的看作一个整体便于查询的作用。
那么采用整体二分，也可以这样做。
对于时间造成的影响，必然要先把时间靠前的操作了，才能处理时间靠后的询问，
因此，最初按照时间排序。
于是二分值域，按照时间顺序，把操作按c分成两部分，
过程中查询询问，把询问也以c为界分开。
到单独一个节点得到答案。

注意：
1、第k大是从小到大第k个。
2、打的clear标记和tag标记pushdown时谁先谁后要处理好。

自己对拍时发现了一组数据没跑过：

6 6
1 1 5 6
2 1 3 2
1 3 6 2
1 1 6 7
2 1 4 4
2 1 2 3

答案是

6
7
6

但我跑出来是6 6 6
发现就是pushdown顺序的问题，唉，真是线段树都不会写了啊。
发现网上好多人AC的代码跑出来也是6 6 6，hack一波。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#define LL long long
using namespace std;
const int N=50005;
int n,m,root=0,tail=0,ans[N];
bool vis[N];
map<int,int> mp;
struct node
{
    int ls,rs,tag;
    LL sum;
    bool clear;
}tr[2*N];
struct MQ
{
    int opt,a,b,c,t,ans;
}s[N],r[N];
bool cmpc(const MQ &A,const MQ &B) {return (A.opt!=B.opt)?A.opt<B.opt:A.c>B.c;}
bool cmpt(const MQ &A,const MQ &B) {return A.t<B.t;}
void build(int &nd,int lf,int rg)
{
    nd=++tail;
    if(lf==rg) return;
    int mid=(lf+rg)>>1;
    build(tr[nd].ls,lf,mid); build(tr[nd].rs,mid+1,rg);
}
void pushdown(int nd,int rg)
{
    int ls=tr[nd].ls; int rs=tr[nd].rs; int mid=(lf+rg)>>1;
    if(tr[nd].clear) 
    {
        tr[nd].clear=0;
        if(ls) {tr[ls].sum=0; tr[ls].tag=0; tr[ls].clear=1;}
        if(rs) {tr[rs].sum=0; tr[rs].tag=0; tr[rs].clear=1;}
    }
    if(tr[nd].tag)
    {
        if(ls) {tr[ls].tag+=tr[nd].tag; tr[ls].sum+=1LL*tr[nd].tag*(mid-lf+1);}
        if(rs) {tr[rs].tag+=tr[nd].tag; tr[rs].sum+=1LL*tr[nd].tag*(rg-mid);}
        tr[nd].tag=0;
    }
}
void update(int nd)
{
    int ls=tr[nd].ls; int rs=tr[nd].rs; 
    tr[nd].sum=tr[ls].sum+tr[rs].sum;
}
void modify(int nd,int rg,int L,int R)
{
    if(L<=lf&&rg<=R) {tr[nd].tag+=1; tr[nd].sum+=1LL*(rg-lf+1); return;}
    pushdown(nd,rg);
    int mid=(lf+rg)>>1;
    if(L<=mid) modify(tr[nd].ls,mid,L,R);
    if(R>mid) modify(tr[nd].rs,rg,R);
    update(nd);
}
LL query(int nd,int R)
{
    if(L<=lf&&rg<=R) return tr[nd].sum;
    pushdown(nd,rg);
    int mid=(lf+rg)>>1; LL ret=0;
    if(L<=mid)  ret+=query(tr[nd].ls,R);
    if(R>mid) ret+=query(tr[nd].rs,R);
    update(nd);
    return ret;
}
void solve(int L,int R,int rg)
{
    if(L>R) return;
    if(lf==rg) {for(int i=L;i<=R;i++) s[i].ans=lf; return;}
    int mid=(lf+rg)>>1; int cnt=0;
    for(int i=L;i<=R;i++)
    {
        if(s[i].opt==1) {if(s[i].c<=mid) {vis[i]=1; cnt++; modify(root,1,n,s[i].a,s[i].b);} else vis[i]=0;}
        else
        {
            LL ret=query(root,s[i].b);  
            if(1LL*ret>=1LL*s[i].c) {cnt++; vis[i]=1;} else {s[i].c-=ret; vis[i]=0;}
        }
    }
    int p1=L; int p2=L+cnt;
    for(int i=L;i<=R;i++)
    {
        if(vis[i]) {r[p1]=s[i]; p1++;}
        else {r[p2]=s[i]; p2++;}
    }
    for(int i=L;i<=R;i++) s[i]=r[i];
    tr[root].clear=1; tr[root].sum=0; tr[root].tag=0;
    solve(L,L+cnt-1,mid); solve(L+cnt,R,rg);
}
int main()
{
    scanf("%d%d",&n,&m);
    build(root,n); int cnt=0,tot=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&s[i].opt,&s[i].a,&s[i].b,&s[i].c);
        s[i].t=i;
        if(s[i].opt==1) cnt++;
    }
    sort(s+1,s+m+1,cmpc); 
    for(int i=1;i<=cnt;i++)
    {
        if(i==1||s[i].c!=mp[s[i-1].c]) {tot++; mp[tot]=s[i].c;}
        s[i].c=tot;
    }
    sort(s+1,cmpt);
    solve(1,tot);
    sort(s+1,cmpt);
    for(int i=1;i<=m;i++) if(s[i].opt==2) printf("%dn",mp[s[i].ans]);
    return 0;
}