@[违规用户名pbFH$J9W](/user/90027) 思路是啥，能给蒟蒻讲一下吗。
by lfxxx @ 2021-09-20 13:45:56
@[lfxxx](/user/478461)
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 300005
inline int read(int &x)
{
int f = 0;
x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
f |= (ch == '-');
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - 48;
ch = getchar();
}
return f ? -x : x;
}
inline void write(int x)
{
if(!x)
{
putchar(48);
return;
}
if(x < 0)
{
putchar('-');
x = -x;
}
int len = 0, dg[25];
while(x > 0)
{
dg[++len] = x % 10;
x /= 10;
}
for(int i = len; i >= 1; i--)
{
putchar(dg[i] + 48);
}
return;
}
int n, q, tmp1[N], tmp2[N], liner[N], ans[N];
signed main()
{
//freopen("qed3.in", "r", stdin);
//freopen("qed3.out", "w", stdout);
read(n);
read(q);
int s, t;
for(int i = 1; i <= q; i++)
{
read(s);
read(t);
if(s < t)
{
tmp1[s - 1]++;
tmp1[t + 1]--;
liner[s - 1] = max(liner[s - 1], t - ((t - s + 1) & 1));
liner[s] = max(liner[s], t - !((t - s + 1) & 1));
}
if(s > t)
{
tmp2[t - 1]++;
tmp2[s + 1]--;
}
}
/*for(int i = 1; i <= n; i++)
{
tmp1[i] += tmp1[i - 1];
tmp2[i] += tmp2[i - 1];
if(tmp1[i] && tmp2[i])
{
printf("QED");
return 0;
}
}*/
int tot = 0;
for(int i = 1; i <= n; i++)
{
if(ans[i])
{
continue;
}
if(!liner[i])
{
ans[i] = ++tot;
continue;
}
int pos = i;
while(liner[pos] > pos)
{
pos = liner[pos];
}
for(int j = pos; j >= i; j -= 2)
{
ans[j] = ++tot;
}
}
for(int i = 1; i <= n; i++)
{
write(ans[i]);
putchar(' ');
}
return 0;
}
```
by fanypcd @ 2021-09-20 13:46:47
@[违规用户名pbFH$J9W](/user/90027)
想了组数据：
```
5 2
4 2
2 4
```
输出 QED。
by lfxxx @ 2021-09-20 13:53:05
@[lfxxx](/user/478461) 不是，我程序根本没判qed（就是注释的地方），如果不注释就只有15pts（会多判），不注释后您的数据能对。
by fanypcd @ 2021-09-20 13:56:25
比如说 $1\ 7$ 和 $5\ 3$ 这样的，就是QED
by Iam1789 @ 2021-09-20 14:18:50
@[Iam1789](/user/414210) 因为既要往左传又要往右传
by Iam1789 @ 2021-09-20 14:19:21