[BZOJ3110][Zjoi2013]K大数查询
[Zjoi2013]K大数查询Description Solution Code #include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for (int i = (l); i <= (r); i++)
#define per(i,r,l) for (int i = (r); i >= (l); i--)
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define MS(_) memset(_,sizeof(_))
#define debug(...) fprintf(stderr,__VA_ARGS__)
typedef unsigned int ll;
const int N = 50000 + 10;
struct node{
ll sum,tag;
node *lc,*rc;
void modify(int l,int r,ll d) {sum += 1ll * (r-l+1) * d; tag += d;}
void sink(int l,int r);
void update() {sum = (lc ? lc->sum : 0) + (rc ? rc->sum : 0);}
}pool[N * 600],*tail = pool;
inline node *newnode() {return tail++;}
inline void node::sink(int l,int r){
if (!lc) lc = newnode(); lc->modify(l,l+r>>1,tag);
if (!rc) rc = newnode(); rc->modify((l+r>>1)+1,tag);
tag = 0;
}
struct NODE{
node *root;
NODE *LC,*RC;
}POOL[N << 2],*ROOT,*TAIL = POOL;
inline NODE *NEWNODE() {return TAIL++;}
int n,m;
template<typename T> inline void read(T &x){
x = 0; T f = 1; char ch = getchar();
while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
x *= f;
}
inline void BUILD(NODE *(&RT),int L,int R){
RT = NEWNODE(); RT->root = newnode();
if (L == R) return;
int MID = L+R >> 1;
BUILD(RT->LC,L,MID); BUILD(RT->RC,MID+1,R);
}
inline void insert(node *rt,int l,int ql,int qr){
rt->sink(l,r);
if (ql <= l && r <= qr) rt->modify(l,1);
else{
int mid = l+r >> 1;
if (ql <= mid){
if (!rt->lc) rt->lc = newnode(); insert(rt->lc,mid,ql,qr);
}
if (qr > mid){
if (!rt->rc) rt->rc = newnode(); insert(rt->rc,mid+1,qr);
}
rt->update();
}
}
inline void INSERT(NODE *RT,int R,int qr,int pos){
insert(RT->root,1,n,qr);
if (L == R) return;
int MID = L+R >> 1;
if (pos <= MID) INSERT(RT->LC,MID,qr,pos);
else INSERT(RT->RC,R,pos);
}
inline ll query(node *rt,r);
if (ql <= l && r <= qr) return rt->sum;
int mid = l+r >> 1; ll res = 0;
if (ql <= mid && rt->lc) res += query(rt->lc,qr);
if (qr > mid && rt->rc) res += query(rt->rc,qr);
return res;
}
inline void QUERY(NODE *RT,int rank){
if (L == R) {printf("%dn",L); return;}
ll cnt = query(RT->RC->root,qr);
//debug("X = %d,ql = %d,qr = %d,cnt = %dn",(L+R) >> 1,cnt);
int MID = L+R >> 1;
if (cnt < rank) QUERY(RT->LC,rank-cnt);
else QUERY(RT->RC,rank);
}
int main(){
read(n); read(m);
BUILD(ROOT,n);
rep(i,m){ int op,a,b,c;
read(op); read(a); read(b); read(c);
if (op == 1) INSERT(ROOT,c);
else QUERY(ROOT,c);
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |