记录编号	150082	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] K大数查询	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	10.727 s
提交时间	2015-02-27 17:29:36	内存使用	2.45 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long LL;
typedef unsigned int Uint;
const int INF=0x3fffffff;
//==============struct declaration==============
struct Node{
     Node *lc,*rc;
     long long sum,add;
     Node(){lc=rc=NULL;sum=add=0;}
};
//==============var declaration=================
const int MAXN=80050;
int n,m,L,R;
long long sum[MAXN*2],addv[MAXN*2];
Node *BitTree[MAXN];
//==============function declaration============
int lowbit(int x){return x&-x;}
void add_bit(int x);
void add_seg(Node *&o,int l,int r);
long long  query_bit(int x);
long long query_seg(Node *&i,int l,int r,long long add);
void update(Node *&o,int l,int r);
void add_num(int o,int l,int r);
long long query_num(int o,int l,int r,long long add);
//==============main code=======================
int main()
{

    freopen("zjoi13_sequence.in","r",stdin);
    freopen("zjoi13_sequence.out","w",stdout);

    scanf("%d%d",&n,&m);n++;
    for(int i=1;i<=n;i++) BitTree[i]=NULL;
    while (m--){
        int cmd,a,b;long long c;scanf("%d%d%d%lld",&cmd,&a,&b,&c);
        if (cmd==1){
             L=a;R=b;
             add_bit(c);add_num(1,1,n-1);
        }
        else if (cmd==2){
            int low=1,high=n-1,mid;
            L=a;R=b;
            long long Num_Exist=query_num(1,1,n-1,0);
            c=Num_Exist-c+1;
            while (low<high){
                mid=(low+high)>>1;
                long long tmp=query_bit(mid);
                if (tmp<c)     low=mid+1;
                if (tmp>=c)     high=mid;
            }
            printf("%d\n",low);
        }
    }
   return 0;
}
//================fuction code====================
void add_bit(int x){
   while (x<=n){
       add_seg(BitTree[x],1,n-1);
       x+=lowbit(x);
   }
}
void add_seg(Node *&o,int l,int r){
    int m=(l+r)>>1;
    if (o==NULL)  o=new(Node);
    if (L<=l&&r<=R){
        o->add++;
        update(o,l,r);
        return;
    }
    if (m>=L)   add_seg(o->lc,l,m);
    if (m<R)    add_seg(o->rc,m+1,r);
    update(o,l,r);
}
void update(Node *&o,int l,int r){
    o->sum=0;
    if (o->lc!=NULL)    o->sum+=o->lc->sum;
    if (o->rc!=NULL)    o->sum+=o->rc->sum;
    o->sum+=(r-l+1)*o->add;
}
long long query_bit(int x){
    long long res=0;
    while (x>0){
        res+=query_seg(BitTree[x],1,n-1,0);
        x-=lowbit(x);
    }
    return res;
}
long long query_seg(Node *&o,int l,int r,long long add){
    if (o==NULL)    return add*(min(r,R)-max(l,L)+1);
    int m=(l+r)>>1;
    if (L<=l&&r<=R)
        return o->sum+(r-l+1)*add;
    long long Left=0,Right=0;
    if (m>=L)    Left=query_seg(o->lc,l,m,add+o->add);
    if (m<R)    Right=query_seg(o->rc,m+1,r,add+o->add);
    return Left+Right;
}
void add_num(int o,int l,int r){
    if (L<=l&&r<=R){
        addv[o]++;
        sum[o]+=r-l+1;
    }
    else{
        int lc=o*2,rc=o*2+1,m=(l+r)>>1;
        if (m>=L)    add_num(lc,l,m);
        if (m<R)    add_num(rc,m+1,r);
        sum[o]=sum[lc]+sum[rc]+addv[o]*(r-l+1);
    }
}
long long query_num(int o,int l,int r,long long add){
    int lc=o*2,rc=o*2+1,m=(l+r)>>1;
    if (L<=l&&r<=R)
        return sum[o]+add*(r-l+1);
    long long Left=0,Right=0;
    if (m>=L)  Left=query_num(lc,l,m,add+addv[o]);
    if (m<R)  Right=query_num(rc,m+1,r,add+addv[o]);
    return Left+Right;
}