QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#80395 | #5409. Perotation | tricyzhkx | 0 | 3ms | 5752kb | C++14 | 2.7kb | 2023-02-23 16:21:41 | 2023-02-23 16:21:45 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
const int B=1300;
int n,a[100010],id[100010],pos[100010],b[100010],blo[100010],cnt1[1010],L[1010],R[1010];
bool val[100010],d[100010];
struct BIT
{
int s[100010];
void update(int x){for(int i=x;i<=n;i+=i&(-i)) s[i]^=1;}
int query(int x)
{
int ans=0;
for(int i=x;i;i-=i&(-i)) ans^=s[i];
return ans;
}
}T;
void pushdown(int i)
{
int l=L[i],r=R[i];
val[id[l]]=d[l];
for(int j=l+1,s=d[l];j<=r;j++) val[id[j]]=(s^=d[j]);
}
void build(int i)
{
int l=L[i],r=R[i];
for(int j=l;j<=r;j++) d[j]=val[id[j]];
cnt1[i]=d[l];
for(int j=r;j>l;j--) d[j]^=d[j-1],cnt1[i]+=d[j];
}
void update(int x,int y,int z) // a[x] <-- y , val[x] = z
{
int l=L[blo[x]],r=R[blo[x]],p=pos[x];
a[x]=y;val[x]=z;
copy(id+p+1,id+r+1,id+p);
copy(b+p+1,b+r+1,b+p);b[r]=n+1;
for(int i=l;i<=r;i++)
if(y<b[i])
{
copy_backward(id+i,id+r,id+i+1);
copy_backward(b+i,b+r,b+i+1);
id[i]=x;b[i]=y;pos[x]=i;
break;
}
build(blo[x]);
}
void update2(int i,int x,int y) // x ~ y : val^=1
{
int l=L[i],r=R[i];
x=lower_bound(b+l,b+r+1,x)-b;
y=upper_bound(b+x,b+r+1,y)-b;
if(x<=r) cnt1[i]-=d[x],d[x]^=1,cnt1[i]+=d[x];
if(y<r) cnt1[i]-=d[y],d[y]^=1,cnt1[i]+=d[y];
}
void update2(int l,int r,int x,int y)
{
if(l>r || x>y) return;
if(blo[l]==blo[r])
{
pushdown(blo[l]);
for(int j=l;j<=r;j++)
if(x<=a[j] && a[j]<=y) val[j]^=1;
build(blo[l]);
return;
}
pushdown(blo[l]);pushdown(blo[r]);
for(int i=l;i<=R[blo[l]];i++)
if(x<=a[i] && a[i]<=y) val[i]^=1;
for(int i=L[blo[r]];i<=r;i++)
if(x<=a[i] && a[i]<=y) val[i]^=1;
build(blo[l]);build(blo[r]);
for(int i=blo[l]+1;i<blo[r];i++) update2(i,x,y);
}
bool query(int x,int y) // # { a[i]<=y : i>=x }
{
if(x>n) return 0;
int ans=0;
for(int i=x;i<=R[blo[x]];i++)
if(a[i]<=y) ans^=1;
for(int i=blo[x]+1;i<=blo[n];i++)
ans^=(upper_bound(b+L[i],b+R[i]+1,y)-b-L[i])&1;
return ans;
}
int query()
{
for(int i=blo[n];i>=1;i--)
if(cnt1[i])
{
pushdown(i);
for(int j=R[i];;j--)
if(val[j]) return j;
}
return 0;
}
int main()
{
int q,x,y;
cin>>n>>q;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),blo[i]=(i-1)/B+1;
for(int i=1;i<=blo[n];i++) L[i]=(i-1)*B+1,R[i]=min(i*B,n);
iota(id+1,id+n+1,1);
for(int i=n;i>=1;i--) val[i]=T.query(a[i]),T.update(a[i]);
for(int i=1;i<=blo[n];i++)
{
int l=L[i],r=R[i];
sort(id+l,id+r+1,[](int j,int k){return a[j]<a[k];});
for(int j=l;j<=r;j++) b[j]=a[id[j]],pos[id[j]]=j;
build(i);
}
while(q--)
{
scanf("%d%d",&x,&y);
if(x>y) swap(x,y);
int v1=a[x],v2=a[y],t1=query(x,v2-1),t2=query(y+1,v1-1);
update(x,v2,t1);update(y,v1,t2);
update2(x+1,y-1,min(v1,v2)+1,max(v1,v2)-1);
printf("%d\n",query()+1);
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 3ms
memory: 5752kb
input:
2 1 1 2 2 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3736kb
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: 0ms
memory: 5740kb
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: -10
Wrong Answer
time: 2ms
memory: 3736kb
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 1 6 1
result:
wrong answer 5th numbers differ - expected: '6', found: '1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%