【BZOJ2674】Attack

2016.03.22 14:59 Tue | 38次阅读 | 旧日oi | 固定链接 | 源码

题解

整体二分+树状数组+权值线段树

可以把交换看成删除再插入,然后整体二分就好了啊……注意交换是不独立的。

mycode

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define lowbit(x) (x&(-x))
int n,m,cnt,tot,tim,num,top;
int x[N],y[N],z[N],b[N],c[N],ans[N];
int ls[N*200],rs[N*200],val[N*200],root[N],vis[N];
char s[10];
struct node
{
    int x,y,xx,yy,k,id,op;
}q[N<<2],_q[N<<2];
void insert(int &x,int l,int r,int p,int v)
{
    if(!x) {x=++num;ls[x]=rs[x]=val[x]=0;}
    val[x]+=v;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(p<=mid) insert(ls[x],l,mid,p,v);
    else insert(rs[x],mid+1,r,p,v);
}
int query(int x,int l,int r,int L,int R)
{
    if(!x) return 0;
    if(L==l&&R==r) return val[x];
    int mid=(l+r)>>1;
    if(R<=mid) return query(ls[x],l,mid,L,R);
    else if(L>mid) return query(rs[x],mid+1,r,L,R);
    else return query(ls[x],l,mid,L,mid)+query(rs[x],mid+1,r,mid+1,R);
}
void add(int x,int y,int v)
{
    for(;x<=top;x+=lowbit(x)) 
    {
        if(vis[x]!=tim) vis[x]=tim,root[x]=0;
        insert(root[x],1,n,y,v);
    }
}
int query(int x,int y)
{
    int ret=0;
    for(;x;x-=lowbit(x)) 
    if(vis[x]==tim) ret+=query(root[x],1,n,1,y);
    return ret;
}
int get_ans(node &a)
{
    return query(a.xx,a.yy)-query(a.xx,a.y-1)-query(a.x-1,a.yy)+query(a.x-1,a.y-1);
}
void solve(int ql,int qr,int l,int r)
{
    if(ql>qr) return;
    int mid=(l+r)>>1,tl=ql,tr=qr;
    tim++;num=0;
    for(int i=ql;i<=qr;i++)
    {
        if(q[i].op==0) 
        {
            int k=get_ans(q[i]);
            if(k>=q[i].k) ans[q[i].id]=mid,_q[tl++]=q[i];
            else _q[tr--]=q[i],_q[tr+1].k-=k; 
        }
        else
        {
            if(q[i].k<=mid) add(q[i].x,q[i].y,q[i].op),_q[tl++]=q[i];
            else _q[tr--]=q[i];
        }
    }
    if(l==r) return;
    for(int i=ql;i<tl;i++) q[i]=_q[i];
    for(int i=tl;i<=qr;i++) q[i]=_q[qr+tl-i];
    solve(ql,tl-1,l,mid);
    solve(tl,qr,mid+1,r);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d%d%d",x+i,y+i,z+i),c[i]=y[i];
    sort(c+1,c+n+1);int tc=unique(c+1,c+n+1)-c-1;
    for(int i=1;i<=n;i++) y[i]=lower_bound(c+1,c+tc+1,y[i])-c;
    for(int i=1;i<=n;i++) b[i]=x[i];
    sort(b+1,b+n+1);top=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++) x[i]=lower_bound(b+1,b+top+1,x[i])-b;
    for(int i=1;i<=n;i++) q[++tot].op=1,q[tot].x=x[i],q[tot].y=y[i],q[tot].k=z[i];
    for(int j,k,i=1;i<=m;i++)
    {
        scanf("%s",&s);
        if(s[0]=='Q') 
        {
            tot++;
            scanf("%d%d%d%d%d",&q[tot].x,&q[tot].y,&q[tot].xx,&q[tot].yy,&q[tot].k);
            if(q[tot].x>q[tot].xx) swap(q[tot].x,q[tot].xx);
            if(q[tot].y>q[tot].yy) swap(q[tot].y,q[tot].yy);
            q[tot].x=lower_bound(b+1,b+top+1,q[tot].x)-b;
            q[tot].xx=upper_bound(b+1,b+top+1,q[tot].xx)-b-1;
            q[tot].y=lower_bound(c+1,c+tc+1,q[tot].y)-c;
            q[tot].yy=upper_bound(c+1,c+tc+1,q[tot].yy)-c-1;
            q[tot].id=++cnt;
        }
        else
        {
            scanf("%d%d",&j,&k);j++;k++;
            q[++tot].op=-1;q[tot].x=x[j];q[tot].y=y[j];q[tot].k=z[j];
            q[++tot].op=1;q[tot].x=x[k];q[tot].y=y[k];q[tot].k=z[j];
            q[++tot].op=1;q[tot].x=x[j];q[tot].y=y[j];q[tot].k=z[k];
            q[++tot].op=-1;q[tot].x=x[k];q[tot].y=y[k];q[tot].k=z[k];
            swap(z[j],z[k]);
        }
    }
    memset(ans,-1,sizeof(ans)); 
    solve(1,tot,1,1000000000);
    for(int i=1;i<=cnt;i++) 
    {
        if(ans[i]!=-1) printf("%d\n",ans[i]);
        else puts("It doesn't exist.");
    }
}