P2745 题解

· · 题解

首先，对于窗口的插入删除，为了节省复杂度，我们用双向链表维护。（单向链表不好找插入位置）

“置顶”“置底”两种操作可以通过插入删除解决。

对于“查询”操作，显然是只有顶部到当前窗口的信息是有用的。考虑在当前窗口的大小内维护被覆盖的区域面积。

这里不使用扫描线。注意到窗口数 N 和查询操作数 M 很小，考虑直接暴力维护。

注意到横纵坐标在 [1,32767] 范围内。一个一个格子维护并不现实。考虑离散化，把格子划分在一些矩形内。

每次枚举矩形的左端点维护信息即可。

输入时要过滤掉多余的字符。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=70;
int Hash(char x){
    if(x>='A'&&x<='Z')return x-'A'+1;
    if(x>='a'&&x<='z')return (x-'a'+1)+('Z'-'A'+1);
    return (x-'0'+1)+('z'-'a'+1)+('Z'-'A'+1);
}
struct Matrix{int X1,X2,Y1,Y2,pre,nxt;}a[N];
void Delete(int x){
    a[a[x].pre].nxt=a[x].nxt;
    a[a[x].nxt].pre=a[x].pre;
}
void Insert(int pos,int x){
    a[x].pre=pos;
    a[x].nxt=a[pos].nxt;
    a[a[pos].nxt].pre=x;
    a[pos].nxt=x;
}
int bottom=N-1;
int x[N*2],cntx,y[N*2],cnty;
unordered_map<int,int>lsx,lsy;
bool vis[N*2][N*2];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    a[bottom].pre=0;a[0].nxt=bottom;
    int T;cin>>T;
    char op;
    while(cin>>op){
        char _1,_2,_3,_4,_5,_6,ID;
        if(op=='w'){
            cin>>_1>>ID;
            int id=Hash(ID);
            Insert(0,id);
            cin>>_2>>a[id].X1>>_3>>a[id].Y1>>_4>>a[id].X2>>_5>>a[id].Y2>>_6;
            if(a[id].X1>a[id].X2)swap(a[id].X1,a[id].X2);
            if(a[id].Y1>a[id].Y2)swap(a[id].Y1,a[id].Y2);
        }
        else{
            cin>>_1>>ID>>_2;int id=Hash(ID);
            if(op=='d')Delete(id);
            if(op=='b')Delete(id),Insert(a[bottom].pre,id);
            if(op=='t')Delete(id),Insert(0,id);
            if(op=='s'){
                lsx.clear();lsy.clear();cntx=cnty=0;
                memset(vis,0,sizeof vis);
                for(int i=a[0].nxt;i!=a[id].nxt;i=a[i].nxt){
                    x[++cntx]=a[i].X1,x[++cntx]=a[i].X2;
                    y[++cnty]=a[i].Y1,y[++cnty]=a[i].Y2;
                }
                sort(x+1,x+1+cntx);
                sort(y+1,y+1+cnty);
                cntx=unique(x+1,x+1+cntx)-x-1;
                cnty=unique(y+1,y+1+cnty)-y-1;
                for(int i=1;i<=cntx;++i)lsx[x[i]]=i;
                for(int i=1;i<=cnty;++i)lsy[y[i]]=i;
                for(int p=a[0].nxt;p!=id;p=a[p].nxt){
                    for(int i=lsx[a[p].X1];i<lsx[a[p].X2]/*i 是当前块的左边界*/;++i)
                    for(int j=lsy[a[p].Y1];j<lsy[a[p].Y2]/*i 是当前块的左边界*/;++j)
                    vis[i][j]=1;
                }
                int ans=0;
                int p=id;
                    for(int i=lsx[a[p].X1];i<lsx[a[p].X2]/*i 是当前块的左边界*/;++i)
                    for(int j=lsy[a[p].Y1];j<lsy[a[p].Y2]/*i 是当前块的左边界*/;++j){
                        if(!vis[i][j])ans+=(x[i+1]-x[i])*(y[j+1]-y[j]);
                    }
                ans*=100;
                double S= (a[id].X2-a[id].X1)*(a[id].Y2-a[id].Y1);
                cout<<fixed<<setprecision(3)<<(ans*1.0/S)<<'\n';
            }
        }
    }
    return 0;
}