QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#127261 | #5409. Perotation | 1kri | 0 | 1ms | 5936kb | C++14 | 2.8kb | 2023-07-19 14:54:38 | 2023-07-19 14:54:42 |
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=320;
int B_tot,B_pos[1005],B_id[100005];
int f[100005],_f[100005];
void upd(int x){
int id=B_id[x]-1;
int cnt=T[id].ask(a[x]);
for (int i=B_pos[id]-1;i>x;i--)
if (a[i]<a[x])cnt++;
f[x]=(cnt&1);
return;
}
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++){
ch[id][i]^=ch[id][i-1];
_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: 1ms
memory: 3728kb
input:
2 1 1 2 2 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: -10
Wrong Answer
time: 1ms
memory: 5936kb
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:
5 10 10 7 10 9 9
result:
wrong answer 1st numbers differ - expected: '7', found: '5'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%