过题数 |
排名 |
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] 的逆序对数量为偶数或者奇数,所有区间要么是包含关系要么不相交。
显然这些区间满足了一个树状的结构,因此可以考虑优先处理小的区间在处理大的区间。
我们可以先设 ai=i ,对于不包含区间的区间,如果要求逆序对为奇数,直接交换相邻的两个数即可。这样还不会影响到别的区间的答案。
如果包含区间的区间,假设 [l,r] 包含了 [l1,r1],[l2,r2],[l3,r3] 三个不相交的区间(他们的子区间我们不用考虑了)这个时候如果三个子区间加起来有奇数个逆序对, [l,r] 要求有偶数个逆序对,这时候就假设我们把所有不在这三个区间的东西也看作几个区间
[l,r]=[l0,r0]+[l1,r1]+[l12,r12]+[l2,r2]+[l23,r23]+[l3,r3]
可以证明我们能找到至少两个区间,比如我们取 [l0,r0],[l1,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]); } }
}
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]<<' '; }
|