QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#83346 | #5409. Perotation | zhouhuanyi | 10 | 5ms | 13920kb | C++23 | 4.5kb | 2023-03-01 14:35:41 | 2023-03-01 14:35:42 |
Judging History
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%