CF gym102979 K. Knowledge Is...

题面传送门
一般图最大匹配是\(O(n^3)\)的，别想了。
我们考虑一个很逊的贪心：先按\(y\)排序，然后按\(y\)从大到小，对于每个区间，到后面找\(x\)最小的未匹配的并且能和它匹配的区间匹配。
如果不能匹配，那么就扔到一个set里面。
然后就可以得到WA on test 7的好成绩。
仔细思考，发现有一组反例：

如果按照\(y\)排序，那么4 6会先和7 8匹配，然后后面不能匹配，最大匹配为1
但是实际上可以1 5和7 8匹配，剩下两个匹配，最大匹配为2
所以我们需要引入反悔操作。
对于当前的一个区间，我们去所有已匹配的且可以和它匹配的区间里找\([l,r]\)区间，满足\([l,r]\)区间原配的区间\(x\)大于当前区间的\(x\)，那么根据贪心，肯定是要找最大的\(x\)拿来换。这个用两个set就可以维护。
时间复杂度大常数\(O(nlogn)\)
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N 300000
#define M 500000
#define mod 1000000007
#define Mod (mod-1)
#define eps (1e-5)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (m*x+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
using namespace std;
int n,m,k,X[N+5],Y[N+5],Ans[N+5],Cnt;
struct Q1{int x,y,id;bool operator <(const Q1 &B)const{return y^B.y?y T1,T2,T3;set::it P1,P2;
int main(){
//	freopen("1.in","r",stdin);
	RI i;scanf("%d%d",&n,&m);for(i=1;i<=n;i++) scanf("%d%d",&X[i],&Y[i]),S[i].x=X[i],S[i].y=Y[i],S[i].id=i;sort(S+1,S+n+1);
	for(i=n;i;i--){
		P1=T1.lower_bound((Q2){S[i].y+1,0,0});if(P1==T1.end()) {//printf("In %d %d %d %d %d\n",i,S[i].x,S[i].y,S[i].id,T1.size());
			P1=P2=T2.lower_bound((Q2){S[i].y+1,0,0});for(;P2!=T2.end();P2++) T3.insert((Q2){X[(*P2).I2],(*P2).I1,(*P2).I2});T2.erase(P1,T2.end());
			if(T3.empty()) T1.insert((Q2){S[i].x,S[i].y,S[i].id})/*,printf("%d %d %d\n",S[i].x,S[i].y,S[i].id)*/;else{
				P2=T3.end(),P2--;Tp=*P2;T3.erase(P2);Ns=(Q2){X[Tp.I1],Tp.I2,Tp.I1};T3.count(Ns)&&(T3.erase(Ns),0);Ns.x=X[Tp.I2];T2.count(Ns)&&(T2.erase(Ns),0);
				//for(RI j=1;j<=n;j++) printf("%d ",Ans[j]);Pc('\n');
				Ans[S[i].id]=Ans[Tp.I1];Ans[Tp.I2]=0;T1.insert((Q2){X[Tp.I2],Y[Tp.I2],Tp.I2});T2.insert((Q2){S[i].x,S[i].id,Tp.I1});T2.insert((Q2){X[Tp.I1],Tp.I1,S[i].id}); 
				//for(RI j=1;j<=n;j++) printf("%d ",Ans[j]);Pc('\n');
			} continue;
		}Ans[S[i].id]=Ans[(*P1).I2]=++Cnt;T2.insert((Q2){S[i].x,S[i].id,(*P1).I2});T2.insert((Q2){X[(*P1).I2],(*P1).I2,S[i].id});T1.erase(P1);
	}for(i=1;i<=n;i++) !Ans[i]&&(Ans[i]=++Cnt),printf("%d ",Ans[i]>m?0:Ans[i]);
}

反悔贪心

CF gym102979 K. Knowledge Is...

相关

标签