51Nod1336 RMQ逆问题 其他

原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1336.html

题目传送门 - 51Nod1336

题意

题解

　　我们将输入的一个区间的答案称为 V 。

　　我们考虑存在排列的两个充分必要条件：

　　1.　一个值 V 只会出现在 询问结果为 V 的区间 的 交 中。

　　2.　对于任意一个 V ，所有询问结果不大于 V 的区间的并中，只可能出现不大于 V 的值。

　　于是我们只需要按照询问区间的 V 从小到达排序，然后依次处理即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=205;

int read(){

	int x=0;

	char ch=getchar();

	while (!isdigit(ch))

		ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+ch-48,ch=getchar();

	return x;

}

struct HashTable{

	int v[N],n;

	void clear(){n=0;}

	void push(int x){v[++n]=x;}

	void Hash(){sort(v+1,v+n+1);n=unique(v+1,v+n+1)-v-1;}

	int find(int x){return lower_bound(v+1,v+n+1,x)-v;}

}p,v;

int T,n,m;

vector <int> vs[N];

struct Seg{

	int L,R,v;

	Seg(){}

	Seg(int _L,int _R,int _v){

		L=_L,R=_R,v=_v;

	}

}s[N],t[N];

bool Getline(){

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

		s[i].L=read();

		s[i].R=read();

		s[i].v=read();

		p.push(s[i].L),p.push(s[i].L+1);

		p.push(s[i].R),p.push(s[i].R+1);

		v.push(s[i].v);

	}

	p.Hash();

	v.Hash();

	for (int i=1;i<=v.n;i++)

		vs[i].clear();

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

		s[i].L=p.find(s[i].L);

		s[i].R=p.find(s[i].R);

		s[i].v=v.find(s[i].v);

		vs[s[i].v].push_back(i);

	}

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

		int L=-1,R=p.n+1;

		for (vector <int> :: iterator p=vs[i].begin();p!=vs[i].end();p++){

			L=max(L,s[*p].L);

			R=min(R,s[*p].R);

		}

		if (L>R)

			return 0;

		t[i]=Seg(L,R,v.v[i]);

	}

	return 1;

}

int cover[N];

void solve(){

	p.clear(),v.clear();

	n=read(),m=read();

	if (!Getline()){

		puts("Impossible");

		return;

	}

	memset(cover,0,sizeof cover);

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

		int cnt=0,L=t[i].L,R=t[i].R,val=v.v[i];

		for (int j=L;j<=R;j++)

			if (!cover[j])

				cnt+=p.v[j+1]-p.v[j];

		for (vector <int> :: iterator P=vs[i].begin();P!=vs[i].end();P++)

			for (int j=s[*P].L;j<=s[*P].R;j++)

				cover[j]=1;

		int tot=0;

		for (int j=1;j<=p.n;j++)

			if (cover[j])

				tot+=p.v[j+1]-p.v[j];

		if (cnt==0||tot>v.v[i]){

			puts("Impossible");

			return;

		}

	}

	puts("Possible");

}

int main(){

	T=read();

	while (T--)

		solve();

	return 0;

}