BZOJ-3110: [Zjoi2013]K大数查询 题解（树状
2018-10-03 本文已影响10人
AmadeusChan
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3110
思路：用树状数组套线段树求解。
首先，将所有操作离线，然后对要插入的所有数进行离散化，然后每个树状数组节点上建议一棵维护权值的线段树，线段树节点[l,r]维护的即是排名从l到r的数的数目。然后用主席树的方法进行查询第K最值，用处理树状数组区间加的方法（https://www.jianshu.com/p/b93b3a55d21e）处理前缀和。最后，由于每个节点都建立一棵完整的线段树会超时超空间，所以线段树要动态建树，最开始树状数组的索引数组上都是一个空节点，在需要修改的时候才拓展出其他要修改用的线段树节点，这样就将总空间复杂度从O(n^2)降到了O(n log n)，时间复杂度也降到了O(n log^2 n)，可以通过此题。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAXN 50001
#define lowbit(x)(((~(x))+1)&x)
#define MAXM 20
int d[MAXN],a[MAXN],b[MAXN],c[MAXN];
int N,M,m=0,R=0;
int r[MAXN];
int MM[MAXN];
struct saver {
int v,t;
} w[MAXN];
bool cmp(saver x,saver y){
return x.v>y.v;
}
struct node {
int l,r,s;
node *left,*right;
node (){
left=right=NULL;
}
};
node *t0[MAXN],*t1[MAXN];
void Build(int l,int r,node *t){
t->l=l;
t->r=r;
t->s=0;
if (l==r) return ;
Build(l,(l+r)>>1,t->left=new(node));
Build(((l+r)>>1)+1,r,t->right=new(node));
}
void Add(int x,int y,node *t){
t->s+=y;
if (t->l==t->r) return ;
int mid=(t->l+t->r)>>1;
if (x<=mid){
if (!t->left){
t->left=new(node);
t->left->l=t->l;
t->left->r=mid;
t->left->s=0;
}
Add(x,y,t->left);
} else {
if (!t->right){
t->right=new(node);
t->right->l=mid+1;
t->right->r=t->r;
t->right->s=0;
}
Add(x,y,t->right);
}
}
int main(){
scanf("%d%d",&N,&M);
for (int i=0;i++<M;){
scanf("%d%d%d%d",&d[i],&a[i],&b[i],&c[i]);
if (d[i]==1){
w[m].v=c[i];
w[m++].t=i;
}
}
sort(w,w+m,cmp);
r[w[0].t]=1;
MM[1]=w[0].v;
R=1;
for (int i=1;i<m;i++){
if (w[i].v!=w[i-1].v)
MM[++R]=w[i].v;
r[w[i].t]=R;
}
memset(t0,0,sizeof(t0));
memset(t1,0,sizeof(t1));
Build(1,R,t0[0]=new(node));
Build(1,R,t1[0]=new(node));
for (int i=0;i++<N;){
t0[i]=new(node);
t0[i]->l=1;
t0[i]->r=R;
t0[i]->s=0;
t1[i]=new(node);
t1[i]->l=1;
t1[i]->r=R;
t1[i]->s=0;
}
for (int I=0;I++<M;){
if (d[I]==1){
int i=a[I];
while (i<=N){
Add(r[I],1,t0[i]);
Add(r[I],a[I],t1[i]);
i+=lowbit(i);
}
i=b[I]+1;
while (i<=N){
Add(r[I],-1,t0[i]);
Add(r[I],-b[I]-1,t1[i]);
i+=lowbit(i);
}
} else {
node *c1[MAXM],*c2[MAXM],*c3[MAXM],*c4[MAXM];
int m1=0,m2=0;
int i=b[I];
while (i){
c1[++m1]=t0[i];
c2[m1]=t1[i];
i-=lowbit(i);
}
i=a[I]-1;
while (i){
c3[++m2]=t0[i];
c4[m2]=t1[i];
i-=lowbit(i);
}
node *t=t0[0];
while (t->l!=t->r){
long long sum1=0,sum2=0;
for (int i=0;i++<m1;){
if (c1[i]) {
if (c1[i]->left) sum1+=(b[I]+1)*c1[i]->left->s;
}
if (c2[i]) {
if (c2[i]->left) sum1-=c2[i]->left->s;
}
}
for (int i=0;i++<m2;){
if (c3[i]) {
if (c3[i]->left) sum2+=a[I]*c3[i]->left->s;
}
if (c4[i]) {
if (c4[i]->left) sum2-=c4[i]->left->s;
}
}
long long sum=sum1-sum2;
if (sum>=c[I]) {
t=t->left;
for (int i=0;i++<m1;){
if (c1[i]) c1[i]=c1[i]->left;
if (c2[i]) c2[i]=c2[i]->left;
}
for (int i=0;i++<m2;){
if (c3[i]) c3[i]=c3[i]->left;
if (c4[i]) c4[i]=c4[i]->left;
}
} else {
c[I]-=sum;
t=t->right;
for (int i=0;i++<m1;){
if (c1[i]) c1[i]=c1[i]->right;
if (c2[i]) c2[i]=c2[i]->right;
}
for (int i=0;i++<m2;){
if (c3[i]) c3[i]=c3[i]->right;
if (c4[i]) c4[i]=c4[i]->right;
}
}
}
printf("%d\n",MM[t->l]);
}
}
return 0;
}
