题解 block

如果不想让next_permutation()自动忽略重复元素，可以在比较函数里加个rk之类的东西使它们不同（next_permutation()不用等于号）

关于第一问：貌似也是一个挺常见的思路

题目要求满足「在位置\(i\)之前比\(val[i]\)大的数严格小于\(k[i]\)个的序列」的个数

考虑这样一种构造方法

把每个二元组按\(val\)降序，\(k\)升序排序，依次加入序列

那么先加入的元素一定大于等于这个元素，不必考虑顺序

所以它能放的位置是前\(k[i]-1\)个空（包括最前面）

而因为不必考虑之前加入的数的顺序，所以消除了后效性

特别注意\(val[i]=val[i+1]\)的情况

\(i+1\)能选择的位置数同样会扩展，而因为前面有\(val\)相同的元素，且这些相同元素的位置此元素也能取到（\(k\)作为第二关键字升序

所以k也相当于扩展了写了一下午就因为没想明白这个

还有数据好像假了排列本来不应该考虑完全相同元素的顺序的，但数据考虑进去了

然后考虑如何构造出一个字典序最小的排列

还是考虑之前平衡树那个思路，维护一棵平衡树，每次取最小的，按\(key[i]\)的位置

好吧平衡树写法不太懂，还是说线段树思路吧

考虑维护一个已选集合和一个未选集合，未选集合按字典序排序

每当我们选一个字典序小的元素为已选，因为其\(val\)值可能较大

考虑\(key\)值的实际意义是比这个元素\(val\)值大且先被选为已选的元素最多有多少个

所以每次把所有\(val\)小于当前\(val\)的元素\(key\)值减一

然后如果有元素\(key\)值已经减成1了，那就不能再先选\(val\)比它大的元素了

这时候把它选上就好了

顺带一提，下面的写法看起来好像「把所有\(val\)小于当前\(val\)的元素\(key\)值减一」的时候还减了一部分\(val\)相等的

但实际上排序时\(key\)作为第二关键字升序，\(key\)值相同时还优先选左边的，所以它的左边不会再有等于它的了

Code:

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define N 500010

#define ll long long

#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)

inline int read() {

	int ans=0, f=1; char c=getchar();

	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}

	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}

	return ans*f;

}

int n;

const ll mod=1e9+7;

struct point{int val, key, rk; inline void build(int v_, int k_) {val=v_; key=k_;}}p[N], bkp[N];

//inline bool operator < (point a, point b) {return a.key==b.key?a.val<b.val:a.key<b.key;}

inline bool operator < (point a, point b) {return a.val==b.val?a.key<b.key:a.val>b.val;}

inline bool cmp1(point a, point b) {return a.val==b.val?a.key<b.key:a.val<b.val;}

inline bool cmp2(point a, point b) {return a.key==b.key?a.val<b.val:a.key<b.key;}

namespace force1{

	ll ans;

	bool first=1;

	void solve() {

		sort(p+1, p+n+1);

		do {

			for (int i=1,cnt; i<=n; ++i) {

				cnt=0;

				for (int j=1; j<i; ++j)

					if (p[i].val<p[j].val) {if (++cnt>=p[i].key) goto jump;}

			}

			++ans;

			if (first) {

				for (int i=1; i<=n; ++i) bkp[i]=p[i];

				first=0;

			}

			jump: ;

		} while (next_permutation(p+1, p+n+1));

		printf("%lld\n", ans%mod);

		for (int i=1; i<=n; ++i) printf("%lld %lld\n", bkp[i].key, bkp[i].val);

		exit(0);

	}

}

namespace task{

	ll ans=1;

	bool vis[N];

	int tl[N<<2], tr[N<<2], minn[N<<2], mini[N<<2], tag[N<<2];

	#define tl(p) tl[p]

	#define tr(p) tr[p]

	#define minn(p) minn[p]

	#define mini(p) mini[p]

	#define tag(p) tag[p]

	inline void pushup(int p) {

		if (minn(p<<1)<=minn(p<<1|1)) minn(p)=minn(p<<1), mini(p)=mini(p<<1);

		else minn(p)=minn(p<<1|1), mini(p)=mini(p<<1|1);

	}

	inline void spread(int p) {

		if (!tag(p)) return ;

		minn(p<<1)-=tag(p), tag(p<<1)+=tag(p);

		minn(p<<1|1)-=tag(p), tag(p<<1|1)+=tag(p);

		tag(p)=0;

	}

	void build(int p2, int l, int r) {

		tl(p2)=l; tr(p2)=r;

		if (l==r) {minn(p2)=p[l].key; mini(p2)=l; return ;}

		int mid=(l+r)>>1;

		build(p2<<1, l, mid);

		build(p2<<1|1, mid+1, r);

		pushup(p2);

	}

	void upd(int p, int pos) {

		if (tl(p)==tr(p)) {minn(p)=INF; vis[tl(p)]=1; return ;}

		spread(p);

		int mid=(tl(p)+tr(p))>>1;

		if (pos<=mid) upd(p<<1, pos);

		else upd(p<<1|1, pos);

		pushup(p);

	}

	void upd(int p, int l, int r) {

		if (l<=tl(p) && r>=tr(p)) {--minn(p); ++tag(p); return ;}

		spread(p);

		int mid=(tl(p)+tr(p))>>1;

		if (l<=mid) upd(p<<1, l, r);

		if (r>mid) upd(p<<1|1, l, r);

		pushup(p);

	}

	void solve() {

		sort(p+1, p+n+1);

		//for (int i=1; i<=n; ++i) cout<<p[i].val<<' '<<p[i].key<<endl;

		int same=0, same2=0;

		for (int i=1; i<=n; ++i) {

			if (i!=1 && p[i].val==p[i-1].val) ++same;

			else same=0;

			ans=ans*min(i, p[i].key+same)%mod;

		}

		printf("%lld\n", ans%mod);

		sort(p+1, p+n+1, cmp1);

		memcpy(bkp+1, p+1, sizeof(point)*n);

		for (int i=1; i<=n; ++i) p[i].rk=i;

		build(1, 1, n);

		sort(p+1, p+n+1, cmp2);

		//for (int i=1; i<=n; ++i) cout<<p[i].key<<' '<<p[i].val<<endl;

		for (int i=1,tn,ti,pos=1; i<=n; ++i) {

			tn=minn(1), ti=mini(1);

			//cout<<"minn: "<<minn(1)<<endl;

			//cout<<"vis: "; for (int i=1; i<=n; ++i) cout<<vis[i]<<' '; cout<<endl;

			if (minn(1)==1) {

				//cout<<"pos1"<<endl;

				//cout<<minn(1)<<' '<<mini(1)<<endl;

				upd(1, ti);

				upd(1, 1, ti);

				printf("%lld %lld\n", bkp[ti].key, bkp[ti].val);

			}

			else {

				//cout<<"pos2"<<endl;

				while (vis[p[pos].rk]) ++pos; //, cout<<"pos: "<<pos<<endl;

				ti=pos;

				upd(1, p[pos].rk);

				upd(1, 1, p[pos].rk);

				printf("%lld %lld\n", p[ti].key, p[ti].val);

			}

		}

		exit(0);

	}

}

signed main()

{

	n=read();

	for (int i=1; i<=n; ++i) p[i].key=read(), p[i].val=read();

	//force1::solve();

	task::solve();

	return 0;

}

巴特西

题解 block

最新文章

热门文章