对于某张卡片，操作可分为三类： Ta < min(Ai,Bi) < =Tb < max(Ai,Bi) < =Tc 对于Ta操作，没有影响。 对于Tb操作，大的那一面一定朝上。 对于Tc操作，每次都会翻一面。 所以我们只要找到每张卡片对应的最后一次Tb，再计算此之后有多少Tc即可。 权值离散化后，建权值线段树，第一个问题相当于区间最大值，第二个问题相当于有时间顺序的区间和，Tc按从大到小顺序加入，询问Tb到结束的和。时间复杂度O(n log n)
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=200100; int a[maxn<<2],b[maxn][2],c[maxn],d[maxn<<2],n,m,size; bool mark[maxn]; struct node { int t,id; }last[maxn]; struct tree { tree *ls,*rs; int l,r,mx,sum; tree() { ls=rs=NULL; mx=sum=0; } void update() { mx=max(ls->mx,rs->mx); sum=ls->sum+rs->sum; } void build(int lx,int rx) { l=lx;r=rx; if(l==r) { mx=sum=d[l]; return ; } int mid=(l+r)>>1; (ls=new tree)->build(l,mid); (rs=new tree)->build(mid+1,r); update(); } int qmax(int lx,int rx) { if(lx>rx) return 0; if(l==lx&&r==rx) return mx; int mid=(l+r)>>1; if(rx<=mid) return ls->qmax(lx,rx); else if(lx>mid) return rs->qmax(lx,rx); else return max(ls->qmax(lx,mid),rs->qmax(mid+1,rx)); } void add(int pl) { if(l==r) {sum++; return ;} int mid=(l+r)>>1; if(pl<=mid) ls->add(pl); else rs->add(pl); update(); } int qsum(int lx,int rx) { if(lx>rx) return 0; if(l==lx&&r==rx) return sum; int mid=(l+r)>>1; if(rx<=mid) return ls->qsum(lx,rx); else if(lx>mid) return rs->qsum(lx,rx); else return ls->qsum(lx,mid)+rs->qsum(mid+1,rx); } }; bool cmp(node a,node b) { return a.t>b.t; } int main() { freopen("card.in","r",stdin); freopen("card.out","w",stdout); cin>>n>>m; memset(mark,0,sizeof(mark)); for(int i=1;i<=n;i++) { scanf("%d%d",&a[2*i-1],&a[2*i]); if(a[2*i-1]>a[2*i]) { swap(a[2*i-1],a[2*i]); mark[i]=1; } b[i][0]=a[2*i-1];b[i][1]=a[2*i]; } for(int i=1;i<=m;i++) { scanf("%d",&a[2*n+i]); c[i]=a[2*n+i]; } sort(a+1,a+2*n+m+1); for(int i=1;i<=n;i++) for(int j=0;j<=1;j++) b[i][j]=lower_bound(a+1,a+2*n+m+1,b[i][j])-a; for(int i=1;i<=m;i++) { c[i]=lower_bound(a+1,a+2*n+m+1,c[i])-a; d[c[i]]=i; } size=2*n+m; tree *xtr; (xtr=new tree)->build(1,size); for(int i=1;i<=n;i++) { last[i].t=xtr->qmax(b[i][0],b[i][1]-1); last[i].id=i; if(last[i].t!=0&&mark[i]==0) mark[i]=1; } sort(last+1,last+n+1,cmp); memset(d,0,sizeof(d)); xtr->build(1,size); int pnt=1; for(int i=m;i>=0;i--) { while(pnt<=n&&last[pnt].t==i) { int o=xtr->qsum(b[last[pnt].id][1],size); mark[last[pnt].id]^=(o&1); pnt++; } if(i!=0)xtr->add(c[i]); } long long ans=0; for(int i=1;i<=n;i++) ans+=a[b[i][mark[i]]]; cout<<ans; return 0; }