了解题意之后，没有思路。。参考了别人的博客，这个题目的解题思路就是维护分量，
将原来的一个长度分解成三个长度，然后加以维护，维护通过pushUp操作来完成，维
护的步骤按照价格的高低。
#include<cstdio> #include<algorithm> using namespace std; const int maxn=130010;//矩形个数 struct edge{ int x1,x2,y,s; int f;//1入，-1出 edge(){} edge(int _x1,int _x2,int _y,int _s,int _f) { x1=_x1,x2=_x2,y=_y, s=_s,f=_f; } bool operator <(const edge &e) { if(y!=e.y)return y<e.y; return f>e.f; } }; struct price{ int id,p; bool operator<(const price &prc)const { return p<prc.p; } }; price P[5]; int nSgs; edge Sgs[maxn*2]; int nX; int X[maxn*2]; int len[maxn*4][4]; int cnt[maxn*4][4]; void build(int root,int l,int r) { len[root][1]=len[root][2]=len[root][3]=0; cnt[root][1]=cnt[root][2]=cnt[root][3]=0; if(l==r)return; int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); } //三个分量随着扫描线的变化 void pushUp(int root,int l,int r,int f,int p) { if(cnt[root][3]){ len[root][3]=X[r+1]-X[l]; len[root][2]=0; len[root][1]=0; } else if(cnt[root][2]){ len[root][3]=len[root*2][3]+len[root*2+1][3]; len[root][2]=X[r+1]-X[l]-len[root][3]; len[root][1]=0; } else if(cnt[root][1]){ len[root][3]=len[root*2][3]+len[root*2+1][3]; len[root][2]=len[root*2][2]+len[root*2+1][2]; len[root][1]=X[r+1]-X[l]-len[root][3]-len[root][2]; } else { len[root][3]=len[root*2][3]+len[root*2+1][3]; len[root][2]=len[root*2][2]+len[root*2+1][2]; len[root][1]=len[root*2][1]+len[root*2+1][1]; } } void update(int root,int L,int R,int f,int p,int l,int r) { if(L<=l&&r<=R){ cnt[root][p]+=f; pushUp(root,l,r,f,p); return; } int mid=(l+r)/2; if(mid>=L)update(root*2,L,R,f,p,l,mid); if(mid<R)update(root*2+1,L,R,f,p,mid+1,r); pushUp(root,l,r,f,p); } int bin(int k,int X[],int n) { int l=0,r=n-1,mid; while(l<=r){ mid=(l+r)/2; if(X[mid]==k)return mid; else if(X[mid]>k)r=mid-1; else l=mid+1; } return -1; } int myUnique(int X[],int n)//哈希之前要去重 { int p=1; for(int i=1;i<n;i++){ if(X[i]!=X[i-1])X[p++]=X[i]; } return p; } int main() { //freopen("in.txt","r",stdin); int T; int p=0; scanf("%d",&T); while(T--){ p++; nX=0,nSgs=0; int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ P[i].id=i; scanf("%d",&P[i].p); } sort(P+1,P+1+m); while(n--){ int x1,y1,x2,y2,id; scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&id); X[nX++]=x1,X[nX++]=x2; int k; for(int i=1;i<=m;i++){ if(P[i].id==id)k=i; } Sgs[nSgs++]=edge(x1,x2,y1,k,1); Sgs[nSgs++]=edge(x1,x2,y2,k,-1); } sort(X,X+nX); sort(Sgs,Sgs+nSgs); nX=myUnique(X,nX); build(1,0,nX-1); long long tot=0; for(int i=0;i<nSgs-1;i++){ int l=bin(Sgs[i].x1,X,nX); int r=bin(Sgs[i].x2,X,nX)-1; if(l<=r) update(1,l,r,Sgs[i].f,Sgs[i].s,0,nX-1); int l1=len[1][1],l2=len[1][2],l3=len[1][3]; tot+=((long long)(l1*P[1].p+l2*P[2].p+l3*P[3].p))*(Sgs[i+1].y-Sgs[i].y); } printf("Case %d: %lld ",p,tot); } //while(1); }
参考资料