QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#127278 | #5409. Perotation | 1kri | 0 | 2ms | 7844kb | C++14 | 2.6kb | 2023-07-19 15:03:48 | 2023-07-19 15:03:52 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,q,a[100005],x,y;
struct BIT{
int tree[100005];
void add(int p,int v){
while(p<=n)tree[p]+=v,p+=(p&(-p));
return;
}
int ask(int p){
int ans=0;
while(p)ans+=tree[p],p-=(p&(-p));
return ans;
}
}T[325],_T;
const int B=2;
int B_tot,B_pos[1005],B_id[100005];
int f[100005],_f[100005];
int len[325],val[325][325],ch[325][325];
int cnt[325];
void pushup(int id){
int l=B_pos[id],r=B_pos[id-1]-1;
len[id]=0;
for (int i=r;i>=l;i--){
f[i]=((T[id-1].ask(a[i])+_T.ask(a[i]))&1);
_T.add(a[i],1);
}
for (int i=r;i>=l;i--)_T.add(a[i],-1);
for (int i=l;i<=r;i++){
val[id][++len[id]]=a[i];
_f[a[i]]=f[i];
}
sort(val[id],val[id]+1+len[id]);
cnt[id]=0;
for (int i=1;i<=len[id];i++){
ch[id][i]=(_f[val[id][i]]^_f[val[id][i-1]]);
if (ch[id][i]==1)cnt[id]++;
}
for (int i=l;i<=r;i++)_f[a[i]]=0;
return;
}
void pushdown(int id){
int l=B_pos[id],r=B_pos[id-1]-1;
for (int i=1;i<=len[id];i++)_f[val[id][i]]=(_f[val[id][i-1]]^ch[id][i]);
for (int i=l;i<=r;i++)f[i]=_f[a[i]];
for (int i=1;i<=len[id];i++)_f[val[id][i]]=0;
return;
}
int ge(int id,int x){
int l=1,r=len[id],ans=len[id]+1;
while(l<=r){
int mid=(l+r)/2;
if (val[id][mid]>=x)ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
int le(int id,int x){
int l=1,r=len[id],ans=0;
while(l<=r){
int mid=(l+r)/2;
if (val[id][mid]<=x)ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
void mdf(int id,int l,int r){
int pl=ge(id,l),pr=le(id,r);
if (pl<=len[id]&&pr>=1){
ch[id][pl]^=1;
if (ch[id][pl]==0)cnt[id]--;
else cnt[id]++;
ch[id][pr+1]^=1;
if (ch[id][pr+1]==0)cnt[id]--;
else cnt[id]++;
}
return;
}
int main(){
scanf("%d%d",&n,&q);
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
B_pos[0]=n+1;
for (int i=n;i>=1;i--)
if (i==1||(n-i+1)%B==0)B_pos[++B_tot]=i;
for (int i=1;i<=B_tot;i++)
for (int j=B_pos[i];j<B_pos[i-1];j++)B_id[j]=i;
for (int i=1;i<=B_tot;i++){
int p=B_pos[i];
for (int j=n;j>=p;j--)T[i].add(a[j],1);
}
for (int i=1;i<=B_tot;i++)pushup(i);
while(q--){
scanf("%d%d",&x,&y);
if (x>y)swap(x,y);
int l=a[x],r=a[y];
if (l>r)swap(l,r);
swap(a[x],a[y]);
for (int i=1;i<=B_tot;i++){
int p=B_pos[i];
if (p>x&&p<=y)T[i].add(a[y],-1),T[i].add(a[x],1);
}
for (int i=B_id[y]+1;i<=B_id[x]-1;i++)mdf(i,l,r);
pushup(B_id[x]);
if (B_id[x]!=B_id[y])pushup(B_id[y]);
int ans=n+1;
for (int i=1;i<=B_tot;i++){
if (cnt[i]>0)break;
ans=B_pos[i];
}
if (ans>1)pushdown(B_id[ans]+1);
while(ans>1&&f[ans-1]==0)ans--;
printf("%d\n",ans);
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 0ms
memory: 7844kb
input:
2 1 1 2 2 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5720kb
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: 5760kb
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: 2ms
memory: 5780kb
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: 5912kb
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: 2ms
memory: 5724kb
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: 0ms
memory: 5708kb
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: 1ms
memory: 5712kb
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: -10
Wrong Answer
time: 0ms
memory: 5824kb
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 3 5 3 2 3 2
result:
wrong answer 3rd numbers differ - expected: '5', found: '3'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%