过题数 排名 A B C D E F G H I J
4 544 √ √ B √ √ 
1
2
3
4
5
6
|过题数|排名|A|B|C|D|E|F|G|H|I|J|K|L|M|
|-----|----|-|-|-|-|-|-|-|-|-|-|-|-|-|
|     |    | | | | | | | | | | | | | |
√ 赛时过了
B 补题过了

E Red and Blue and Green

构造一个序列，满足区间 [l,r][l,r] 的逆序对数量为偶数或者奇数，所有区间要么是包含关系要么不相交。

显然这些区间满足了一个树状的结构，因此可以考虑优先处理小的区间在处理大的区间。

我们可以先设 ai=ia_i=i ，对于不包含区间的区间，如果要求逆序对为奇数，直接交换相邻的两个数即可。这样还不会影响到别的区间的答案。

如果包含区间的区间，假设 [l,r][l,r] 包含了 [l1,r1],[l2,r2],[l3,r3][l1,r1],[l2,r2],[l3,r3] 三个不相交的区间（他们的子区间我们不用考虑了）这个时候如果三个子区间加起来有奇数个逆序对， [l,r][l,r] 要求有偶数个逆序对，这时候就假设我们把所有不在这三个区间的东西也看作几个区间

[l,r]=[l0,r0]+[l1,r1]+[l12,r12]+[l2,r2]+[l23,r23]+[l3,r3][l,r]=[l0,r0]+[l1,r1]+[l12,r12]+[l2,r2]+[l23,r23]+[l3,r3]

可以证明我们能找到至少两个区间，比如我们取 [l0,r0],[l1,r1][l0,r0],[l1,r1] 这两个区间

把左边的区间的最大值与右边区间的最小值交换，对两个区间的逆序对总数没有任何影响，但是对 [l0,r1][l0,r1] 这个区间来说，奇偶性发生了改变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>

using namespace std;

const int maxn=1010;

int n,m;
int vis[maxn],a[maxn];

struct mmm
{
	int l,r,x;
	bool operator <(const mmm &b)
	{
		if(l==b.l) return r>b.r;
		else return l<b.l;
	}
}q[maxn];

void dfs(int x)
{
	if(vis[x]) return ;
	vis[x]=1;
	int l=q[x].l;
	int r=q[x].r;
	int nowr=l-1;
	int cnt=0;
	int r1=0,r2=0;
	int v=-1;
	for(int i=x+1;q[i].l<=r&&i<=m;i++)
	{
		if(q[i].l>=nowr&&q[i].r<=q[x].r)
		{
			dfs(i);
			nowr=q[i].r+1;
			if(!r1) r1=i;
			else if(!r2) r2=i;
			if(v==-1) v=q[i].x;
			else v+=q[i].x;
			cnt++;
		}
	}
	if(cnt==0&&q[x].x)
	{
		swap(a[q[x].r],a[q[x].r-1]);
	}
	else if(cnt==1&&v!=q[x].x)
	{
		if(q[x].l==q[x+1].l) 
		{
			int mmx=q[r1].l,mmn=q[r1].r+1;
			for(int i=q[r1].l;i<=q[r1].r;i++) if(a[mmx]<a[i]) mmx=i;
			for(int i=q[r1].r+1;i<=q[x].r;i++) if(a[mmn]>a[i]) mmn=i;
			swap(a[mmx],a[mmn]);
		}
		else 
		{
			int mmx=q[x].l,mmn=q[r1].l;
			for(int i=q[x].l;i<q[r1].l;i++) if(a[mmx]<a[i]) mmx=i;
			for(int i=q[r1].l;i<=q[r1].r;i++) if(a[mmn]>a[i]) mmn=i;
			swap(a[mmx],a[mmn]);			
		}
	}
	else if(cnt>=2)
	{
		if(v%2!=q[x].x%2) 
		{
			int mmn=q[r2].l,mmx=q[r1].l;
			for(int i=q[r1].l;i<=q[r1].r;i++) if(a[mmx]<a[i]) mmx=i;
			for(int i=q[r2].l;i<=q[r2].r;i++) if(a[mmn]>a[i]) mmn=i;
			swap(a[mmx],a[mmn]);
		}
	}
//		for(int i=1;i<=n;i++) cout<<a[i]<<" ";
//	cout<<'\n';
//	cout<<q[x].l<<" "<<q[x].r<<" "<<q[x].x<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) a[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>q[i].l>>q[i].r>>q[i].x;
		if(q[i].l==q[i].r&&q[i].x)
		{
			cout<<"-1\n";
			return 0;
		}
	}
	sort(q+1,q+m+1);
	for(int i=1;i<=m;i++)
	{
		if(!vis[i]) dfs(i);
	}
	for(int i=1;i<=n;i++) cout<<a[i]<<' ';
}