QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#83346#5409. Perotationzhouhuanyi10 5ms13920kbC++234.5kb2023-03-01 14:35:412023-03-01 14:35:42

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-01 14:35:42]
  • 评测
  • 测评结果:10
  • 用时:5ms
  • 内存:13920kb
  • [2023-03-01 14:35:41]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<vector>
#include<algorithm>
#define N 100000
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int lowbit(int x)
{
    return x&(-x);
}
int n,q,sz,lg[N+1],a[N+1],b[N+1],c[N+1],block[N+1],num[N+1],ans;
vector<int>p[N+1];
vector<int>v[N+1];
vector<unsigned long long>w[N+1];
unsigned long long seed,rd[N+1],delta[N+1];
unsigned long long RAND()
{
    seed=(seed<<7)^seed;
    seed=(seed>>13)^seed;
    seed=(seed<<17)^seed;
    return seed;
}
void add(int x,int d)
{
    for (;x<=n;x+=lowbit(x)) c[x]^=d;
    return;
}
int query(int x)
{
    int res=0;
    for (;x>=1;x-=lowbit(x)) res^=c[x];
    return res;
}
void spread(int x)
{
    int res=0;
    for (int i=0;i<p[x].size();++i) res^=v[x][i],num[p[x][i]]^=res;
    for (int i=0;i<v[x].size();++i) v[x][i]=0;
    return;
}
void rebuild(int x,int d1,int d2)
{
    bool op=0,op2=0;
    vector<int>q;
    if (d1&&d2&&a[d1]>a[d2]) swap(d1,d2);
    for (int i=0;i<p[x].size();++i)
	if (p[x][i]!=d1&&p[x][i]!=d2)
	{
	    if (!op&&d1&&a[d1]<a[p[x][i]]) op=1,q.push_back(d1);
	    if (!op2&&d2&&a[d2]<a[p[x][i]]) op2=1,q.push_back(d2);
	    q.push_back(p[x][i]);
	}
    if (!op&&d1) q.push_back(d1);
    if (!op2&&d2) q.push_back(d2);
    p[x]=q,delta[x]=0;
    for (int i=0;i<p[x].size();++i)
    {
	w[x][i]=rd[p[x][i]];
	if (num[p[x][i]]) delta[x]^=rd[p[x][i]];
	if (i) w[x][i]^=w[x][i-1];
    }
    return;
}
void change(int x,int l,int r)
{
    int sl=-1,sr=-1;
    for (int i=lg[p[x].size()];i>=0;--i)
	if (sl+(1<<i)<p[x].size()&&a[p[x][sl+(1<<i)]]<l)
	    sl+=(1<<i);
    sl++;
    for (int i=lg[p[x].size()];i>=0;--i)
	if (sr+(1<<i)<p[x].size()&&a[p[x][sr+(1<<i)]]<=r)
	    sr+=(1<<i);
    if (sl<v[x].size()) v[x][sl]^=1;
    if (sr+1<v[x].size()) v[x][sr+1]^=1;
    delta[x]^=(w[x][sr]^(sl?w[x][sl-1]:0));
    return;
}
int query(int x,int l,int r)
{
    int sl=-1,sr=-1;
    for (int i=lg[p[x].size()];i>=0;--i)
	if (sl+(1<<i)<p[x].size()&&a[p[x][sl+(1<<i)]]<l)
	    sl+=(1<<i);
    sl++;
    for (int i=lg[p[x].size()];i>=0;--i)
	if (sr+(1<<i)<p[x].size()&&a[p[x][sr+(1<<i)]]<=r)
	    sr+=(1<<i);
    return (sr-sl+1)&1;
}
void adder(int x,int y)
{
    int res=0,res2=0;
    for (int i=block[x]+1;i<=block[y]-1;++i) res^=query(i,1,a[x]),res2^=query(i,1,a[y]),change(i,min(a[x],a[y]),max(a[x],a[y]));
    if (block[x]==block[y])
    {
	spread(block[x]);
	for (int i=x+1;i<=y-1;++i)
	{
	    if (min(a[x],a[y])<a[i]&a[i]<max(a[x],a[y])) num[i]^=1;
	    if (a[i]<a[x]) res^=1;
	    if (a[i]<a[y]) res2^=1;
	}
	swap(a[x],a[y]),num[x]^=res,num[y]^=res2,swap(num[x],num[y]);
	if (a[x]>a[y]) num[x]^=1;
	else num[y]^=1;
	rebuild(block[x],x,y);
    }
    else
    {
	spread(block[x]),spread(block[y]);
	for (int i=x+1;i<=min(block[x]*sz,n);++i)
	{
	    if (min(a[x],a[y])<a[i]&&a[i]<max(a[x],a[y])) num[i]^=1;
	    if (a[i]<a[x]) res^=1;
	    if (a[i]<a[y]) res2^=1;
	}
	for (int i=(block[y]-1)*sz+1;i<=y-1;++i)
	{
	    if (min(a[x],a[y])<=a[i]&&a[i]<=max(a[x],a[y])) num[i]^=1;
	    if (a[i]<a[x]) res^=1;
	    if (a[i]<a[y]) res2^=1;
	}
	swap(a[x],a[y]),num[x]^=res,num[y]^=res2,swap(num[x],num[y]);
	if (a[x]>a[y]) num[x]^=1;
	else num[y]^=1;
	rebuild(block[x],x,0),rebuild(block[y],y,0);
    }
    return;
}
int calc()
{
    for (int i=1;i<=block[n];++i) spread(i);
    int ps=0;
    for (int i=block[n];i>=1;--i)
	if (delta[i])
	{
	    spread(i);
	    for (int j=min(i*sz,n);j>=(i-1)*sz+1;--j)
		if (num[j])
		{
		    ps=j;
		    break;
		}
	    break;
	}
    return ps+1;
}
bool cmp(int x,int y)
{
    return a[x]<a[y];
}
int main()
{
    int x,y;
    n=read(),q=read(),sz=sqrt(n*log(n)/log(2)),seed=time(0);
    for (int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
    for (int i=1;i<=n;++i) a[i]=read(),block[i]=(i-1)/sz+1,rd[i]=RAND();
    for (int i=n;i>=1;--i) num[i]=query(a[i]),add(a[i],1);
    for (int i=1;i<=block[n];++i)
    {
	for (int j=(i-1)*sz+1;j<=min(i*sz,n);++j) p[i].push_back(j);
	sort(p[i].begin(),p[i].end(),cmp),v[i].resize(p[i].size()),w[i].resize(p[i].size());
	for (int j=0;j<p[i].size();++j)
	{
	    w[i][j]=rd[p[i][j]];
	    if (num[p[i][j]]) delta[i]^=rd[p[i][j]];
	    if (j) w[i][j]^=w[i][j-1];
	}
    }
    while (q--)
    {
	x=read(),y=read();
	if (x>y) swap(x,y);
	adder(x,y),printf("%d\n",calc());
    }
    return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 4ms
memory: 11896kb

input:

2 1
1 2
2 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 11896kb

input:

9 7
3 5 8 2 4 9 1 6 7
2 8
3 1
2 1
1 5
3 8
1 3
9 1

output:

7
7
7
7
7
7
7

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 12288kb

input:

7 7
6 7 2 1 5 3 4
3 1
3 1
7 5
1 6
6 5
6 1
1 7

output:

3
4
6
7
4
4
4

result:

ok 7 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 11988kb

input:

7 7
2 4 3 1 5 6 7
7 6
6 3
3 1
1 4
3 4
2 5
4 1

output:

7
6
6
6
6
6
6

result:

ok 7 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 11820kb

input:

6 6
5 3 1 4 2 6
5 4
5 2
4 3
6 5
1 5
6 4

output:

1
3
4
6
6
6

result:

ok 6 numbers

Test #6:

score: 0
Accepted
time: 3ms
memory: 11868kb

input:

10 9
7 9 2 5 1 6 8 3 4 10
4 5
2 9
10 6
6 1
5 3
10 1
5 7
1 7
8 3

output:

4
8
10
10
10
8
6
8
8

result:

ok 9 numbers

Test #7:

score: 0
Accepted
time: 3ms
memory: 11736kb

input:

8 8
4 2 6 5 8 3 7 1
5 6
2 4
6 5
6 1
4 6
1 2
2 8
8 6

output:

8
8
8
8
8
8
8
8

result:

ok 8 numbers

Test #8:

score: 0
Accepted
time: 4ms
memory: 11724kb

input:

8 8
6 8 4 7 1 3 5 2
1 4
3 8
3 8
8 3
6 2
1 5
1 6
7 4

output:

8
8
8
8
8
8
8
8

result:

ok 8 numbers

Test #9:

score: 0
Accepted
time: 1ms
memory: 11784kb

input:

6 8
6 1 2 5 3 4
6 1
4 5
2 5
5 3
4 6
4 1
2 4
4 2

output:

5
2
5
5
3
2
3
2

result:

ok 8 numbers

Test #10:

score: 0
Accepted
time: 1ms
memory: 13768kb

input:

10 7
3 1 8 7 6 2 9 5 10 4
7 3
10 7
1 3
2 1
8 10
8 3
1 2

output:

10
10
10
10
10
10
10

result:

ok 7 numbers

Test #11:

score: 0
Accepted
time: 1ms
memory: 11828kb

input:

8 7
3 1 4 2 7 5 8 6
6 5
6 5
2 3
5 1
4 8
7 2
5 1

output:

8
8
8
8
8
8
8

result:

ok 7 numbers

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #12:

score: 20
Accepted
time: 4ms
memory: 12152kb

input:

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

output:

90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
89
89
89
89
89
89
89
89
89
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88

result:

ok 83 numbers

Test #13:

score: 0
Accepted
time: 5ms
memory: 13708kb

input:

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

output:

87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
85
85
85
85
85
85
85
85
85
85
83
83
83
83
83
83
83
83
83
83
83
83
85
85
85
85
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87

result:

ok 95 numbers

Test #14:

score: 0
Accepted
time: 5ms
memory: 12268kb

input:

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

output:

83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
84
84
84
84
84
84
84
84
84
84
84
84
84
84
86
86
86
86
86
86

result:

ok 90 numbers

Test #15:

score: 0
Accepted
time: 4ms
memory: 11904kb

input:

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

output:

45
45
45
45
45
45
45
45
45
45
45
45
45
73
74
73
72
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80

result:

ok 71 numbers

Test #16:

score: 0
Accepted
time: 1ms
memory: 13920kb

input:

80 66
26 54 23 35 62 1 25 56 12 48 37 8 80 7 32 40 52 78 69 6 29 10 36 50 16 42 61 60 27 38 14 77 17 9 20 59 64 79 5 76 67 39 18 34 13 71 15 70 66 19 24 63 72 53 2 75 65 51 22 44 73 28 11 3 57 33 30 74 46 55 31 41 43 68 4 47 49 58 21 45
39 1
37 18
35 6
32 3
31 21
31 27
31 46
46 55
54 6
51 19
51 45
5...

output:

40
40
40
40
40
40
47
55
55
55
55
55
55
55
55
55
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
72
72
70

result:

ok 66 numbers

Test #17:

score: 0
Accepted
time: 4ms
memory: 12192kb

input:

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

output:

68
64
68
68
68
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
90
90
90
90
90
90
90
90
90
90
90
90

result:

ok 100 numbers

Test #18:

score: 0
Accepted
time: 0ms
memory: 11868kb

input:

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

output:

78
86
86
1
23
31
23
1
18
1
53
1
90
1
91
1
29
1
55
77
77
77
18
1
85
85
85
1
26
1
54
87
87
1
66
1
73
1
50
82
82
1
80
84
80
1
78
88
94
88
78
1
91
1
79
79
79
1
49
1
65
1
44
1
27
77
27
1
60
60
47
1
92
1
75
1
74
1
57
94
94
87
57
1
68
68
81
81
81
1
47
53
53
1
34
1
33
65
33
1

result:

ok 100 numbers

Test #19:

score: 0
Accepted
time: 1ms
memory: 13828kb

input:

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

output:

96
96
96
1
36
1
56
1
88
1
81
1
68
1
37
1
90
1
28
1
98
98
98
1
55
86
86
1
93
1
84
84
69
69
65
1
99
1
55
1
61
61
42
1
88
1
30
1
38
1
49
49
44
1
96
96
85
85
85
1
50
1
60
60
60
1
45
45
26
1
27
1
42
78
78
1
53
53
100
100
100
1
94
94
64
88
88
1
87
96
96
1
98
98
98
97
97
1
83
1

result:

ok 100 numbers

Test #20:

score: 0
Accepted
time: 1ms
memory: 11880kb

input:

84 83
55 56 13 14 69 70 79 80 3 4 49 50 9 10 27 28 29 30 59 60 73 74 1 2 11 12 77 78 51 52 45 46 15 16 17 18 33 34 31 32 25 26 53 54 43 44 63 64 41 42 39 40 19 20 37 38 81 82 75 76 83 84 23 24 47 48 61 62 5 6 7 8 35 36 21 22 65 66 57 58 71 72 67 68
12 32
11 31
62 82
22 48
21 47
78 72
77 71
68 52
61 ...

output:

13
1
63
63
63
78
63
68
68
1
33
23
33
1
48
1
63
1
33
1
60
1
40
51
80
80
80
1
75
61
74
1
58
1
72
1
31
51
31
1
62
1
39
73
73
79
79
1
67
1
74
75
74
74
74
76
76
1
39
1
4
1
82
82
76
76
76
1
22
23
23
1
78
1
52
1
47
57
57
1
75
1
59

result:

ok 83 numbers

Test #21:

score: -20
Wrong Answer
time: 2ms
memory: 11732kb

input:

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

output:

75
1
33
1
59
1
80
98
98
98
98
98
1
1
80
80
80
80
80
80
80
89
89
1
75
75
75
54
74
74
54
1
48
1
87
87
84
88
88
1
62
1
61
1
95
1
86
86
86
86
30
1
47
1
86
86
39
1
83
1
10
1
90
90
90
1
26
1
41
66
66
1
67
1
94
1
46
1
71
71
70
1
82
1
96
96
96
1
14
68
68
68
40
1
79
79
79
1
48
1

result:

wrong answer 13th numbers differ - expected: '17', found: '1'

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%