Segregacija / PR #13 B 交换豆子

· · 题解

假设 C 是 1，P 是 0。

枚举第一行最后有多少个 1，由于 1 的总个数不变，因此第一/第二行的 1 的个数是确定的。

假设 y 坐标为 [1,2]，x 坐标为 [1,n]，此时我们想要最小化 移动步数 + 最后所有 1 的 x 坐标之和，答案就是这个值减去 \frac{c_1(c_1+1)}{2}+\frac{c_2(c_2+1)}{2}。

上下的移动步数是确定的，只需要最小化向右的移动步数（这些移动步数会增加 x 坐标，每移动一步会有 2 的代价，因为要增大 x 坐标且多移动一次）。

接下来观察一些性质：

什么情况下可以满足要求？若一列有 2 个 1，则这列必须在第二行有一个 1，也就是有 2 个 1 的列不能超过 c_2 个。

对于一个前缀的若干列，设有 sum_i 个 1 和 i 列，则有 \max(0,sum_i-i-c_2) 个 1 必须向右调，需要花费的代价就是 \sum 2\times \max(0,sum_i-i-c_2)。

对于每种 (c_1,c_2) 维护一个 ans_{c_2}，交换同一列两个时 sum_i 不改变；交换不同列时只有 1 个 sum_i 会改变至多 1，只需要在 ans 上区间加。

用线段树维护 ans 数组，时间复杂度 O(n+q\log n)。

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 2000045
#define inf 0x3f3f3f3f3f3f3f3f

int n,q,all,L,R;
int a[maxn][3];
char s[maxn];
int sum,c1,c2,b[maxn];

int C2(int x){
    return x*(x+1)/2;
}

int w[maxn];

int mn[maxn<<2],tag[maxn<<2];
void pt(int p,int v){
    tag[p]+=v,mn[p]+=v;
}
void down(int p){
    if(tag[p]) pt(p<<1,tag[p]),pt(p<<1|1,tag[p]),tag[p]=0;
}
void up(int p){
    mn[p]=min(mn[p<<1],mn[p<<1|1]);
}
void build(int p,int l,int r){
    if(l==r)return mn[p]=w[l],void();
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    up(p);
}
void add(int p,int l,int r,int nl,int nr,int v){
    if(nl>nr)return;
    if(l>=nl&&r<=nr)return pt(p,v);
    int mid=l+r>>1; down(p);
    if(nl<=mid)add(p<<1,l,mid,nl,nr,v);
    if(nr>mid)add(p<<1|1,mid+1,r,nl,nr,v); up(p);
}
int ask(int p,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr)return mn[p];
    int mid=l+r>>1; down(p);
    int res=1e18;
    if(ql<=mid)res=min(res,ask(p<<1,l,mid,ql,qr));
    if(qr>mid)res=min(res,ask(p<<1|1,mid+1,r,ql,qr));
    return res;
}

void swp(int x,int y,int xx,int yy){
    if(a[x][y]==a[xx][yy]) return;
    sum-=a[x][y]*x+a[xx][yy]*xx;
    c1-=(a[x][y] && y==1),c1-=(a[xx][yy] && yy==1);
    swap(a[x][y],a[xx][yy]);
    sum+=a[x][y]*x+a[xx][yy]*xx;
    c1+=(a[x][y] && y==1),c1+=(a[xx][yy] && yy==1);
    c2=all-c1;
    if(x==xx) return;
    if(x>xx) swap(x,xx);
    int lstb=b[x];
    b[x]=b[x-1]+a[x][1]+a[x][2]-1;
    if(b[x]>lstb){
        add(1,L,R,L,b[x]-1,2);
    }
    if(b[x]<lstb){
        add(1,L,R,L,b[x],-2);
    }
}

void prework()
{
//  For(j,1,n)cout<<b[j]<<" "; cout<<" b\n";
//  For(i,1,n) b[i]=b[i-1]+a[i][1]+a[i][2]-1;
    For(i,L,R){
        w[i]=(all-i)-C2(i)-C2(all-i);
        // \sum max(2*(b_i-i),0ll)
    //  For(j,1,n) w[i]+=max(0ll,2*(b[j]-i));
    }
    vi B;
    For(j,1,n) B.pb(b[j]);
    sort(ALL(B));
    int now=0,cnt=0;
    Rep(i,R,L){
        now+=cnt*2;
        while(B.size() && B.back()>=i)
            now+=(B.back()-i)*2,++cnt,B.pop_back();
        w[i]+=now;
    }
    build(1,L,R);
//  For(i,0,L) cout<<w[i]<<" "; cout<<"\n";
}

int getans(){
//  prework();
//  cout<<"sum,c1 "<<sum<<" "<<c1<<"\n";
    int res=inf; //ask(1,0,L,0,min(L,c2));
    res=ask(1,L,R,L,min(R,c2));
//  For(i,L,min(R,c2)) res=min(res,w[i]);
//  cout<<"res "<<res<<"\n";
    res+=sum-c1;
    return res;
}

signed main()
{
//  freopen("b21.in","r",stdin);
//  freopen("my.out","w",stdout);
    n=read(),q=read();
    For(j,1,2){
        scanf("%s",s+1);
        For(i,1,n) a[i][j]=(s[i]=='P'),all+=a[i][j],sum+=a[i][j]*i;
    }
    For(i,1,n)c1+=a[i][1],c2+=a[i][2];
    L=max(0ll,all-n);
    R=(all-(all+1)/2);
    For(i,1,n) b[i]=b[i-1]+a[i][1]+a[i][2]-1;
    prework();
    printf("%lld\n",getans());
    For(i,1,q){
        int op=read(),y=read(),x=read();
        if(op==1) swp(x,y,x+1,y);
        else swp(x,y,x,y+1);
        printf("%lld\n",getans());
    }
    return 0;
}
/*
5 2
CPCPC
PCCPC
1 1 4
1 1 2

10 7
CCPPPCCPCP
PPPCCCPCCC
1 2 7
2 1 4
2 1 8
1 1 9
2 1 1
1 2 7
1 1 4
*/