题意

题解

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

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

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

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

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

代码

#include 
     
      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 
      
        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 
       
         :: 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 
        
          :: 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;}