F. Easy Fix

F. Easy Fix

题目大意

给定一个排序p。定义A[i]为[1,i-1]中小于p[i]的数,B[i]是[i+1,n]中小于p[i]的数。

定义整个排列的贡献为\(\sum_{i=1}^{n}min(A[i],B[i])\)。

现在给出m次操作，每次操作，给出x,y交换排列中p[x],p[y]，每次操作独立。

问每次操作后整个排列的贡献是多少。

分析

我们首先可以发现，\(A[i] + B[i] = p_i – 1\)。

我们观察后，可以发现，如果对于一个区间(l,r)中的某个位置i。

• 如果，\(a[i]<min(p[l],p[r])||a[i]>max(p[l],p[r])\)，那么交换不会有什么影响。
• 因此，我们只需要讨论一下，区间中落在\([min(p[l],p[r]),max(p[l],p[r])]\)的数变化。

而这个问题，我们是可以利用二维数点来解决的。

我们来讨论第二种情况的细分情况。

我们先假设\(p[x]<p[y]\)

• \(A[i]==B[i]\)，原来的\(min(A[i],B[i])=A[i]\)，现在\(min(A[i]-1,B[i]+1)=A[i]-1\)，少1
• \(A[i]==B[i]+1\)，原来的\(min(A[i],B[i])=B[i]\)，现在\(min(A[i]-1,B[i]+1)=B[i]\)，不变
• \(A[i]+1==B[i]\)，原来的\(min(A[i],B[i])=A[i]\)，现在\(min(A[i]-1,B[i]+1)=A[i]-1\)，少1
• \(A[i] \leq B[i] + 2\)，原来的\(min(A[i],B[i])=A[i]\)，现在\(min(A[i]-1,B[i]+1)=A[i]-1\)，少1
• \(A[i] \geq B[i] + 2\)，原来的\(min(A[i],B[i])=B[i]\)，现在\(min(A[i]-1,B[i]+1)=B[i]+1\)，多1

同理，我们可以推出\(p[x]>p[y]\)的结果。

接着我们来讨论一下，对于边界的l,r，对答案的贡献如何计算。

我们可以先将，原来的贡献减去，再重新加上新的贡献。

那新的贡献是什么呢？我们设(l,r)中小于\(p_l,p_r\)的数分别设为\(d_l,d_r\)

我们交换l,r其实就是\(newA[l] = A[l] + d_l,newB[l] = B[l] – d_l\)，\(newA[r] = A[r] – d_r,newB[r] = B[r] + d_r\)。

我们维护这些值，总计需要t1,t2,t3,t4,t5,xx,yy七个二维数点。

AC_code

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;

struct tp {
    // add 添加点
    // que 添加矩形 参数为矩形的左下角，右上角，询问的id 
    // get 传入一个数组，答案会放到数组里面
    static const int maxnum = 2e5 + 5;//数据范围
    static const int maxn = 2e5 + 5;//区间和问题的数量
    int tree[maxnum];
    int n = 0, m = 0;
    struct node1
    {
        int x, y;
    }v[maxn];
    struct node2
    {
        int x, y, id, type;
    } q[maxn << 2];
    static bool cmp1(node1 &a, node1 &b) {
        return a.x < b.x;
    }
    static bool cmp2(node2 &a, node2 &b) {
        return a.x < b.x;
    }
    void update(int idx, int x) {
        while(idx<=maxnum)
        {
            tree[idx] += x;
            idx += idx & -idx;
        }
    }
    int query(int n) {
        int ans = 0;
        while(n)
        {
            ans += tree[n];
            n -= n & -n; 
        }
        return ans;
    }
    int cnt = 0;
    void add(int x, int y) {
        v[++n].x = x, v[n].y = y;
    }
    void que(int x1, int y1, int x2, int y2, int i) {
        q[++cnt] = { x2, y2, i, 1 };
        q[++cnt] = { x1 - 1, y2, i, -1 };
        q[++cnt] = { x2, y1 - 1, i, -1 };
        q[++cnt] = { x1 - 1, y1 - 1, i, 1 };
        m++;
    }
    void get(int *ans) {
        sort(v + 1, v + 1 + n, cmp1);
        sort(q + 1, q + 1 + cnt, cmp2);
        int u = 1;
        for (int i = 1; i <= cnt; i++) {
            while (v[u].x <= q[i].x&&u <= n) {
                update(v[u].y, 1);
                u++;
            }
            ans[q[i].id] += q[i].type * (query(q[i].y));
        }
        for (int i = 1; i <= m; i++) ans[i] = max(ans[i], 0);
    }
};

const int N = 2e5 + 10;

tp t1,t2,t3,t4,t5,xx,yy;
int n,p[N],m,A[N],B[N];
int ans1[N],ans2[N],ans3[N],ans4[N],ans5[N];
int ansxx[N],ansyy[N];
int x[N],y[N];
int tr[N],ans[N];
int sum;

int query(int x)
{
    int res = 0;
    while(x)
    {
        res += tr[x];
        x -= x & -x;
    }
    return res;
}

void add(int x)
{
    while(x<=n)
    {
        tr[x] += 1;
        x += x & -x;
    }
}

int main()
{
    ios;cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++)
    {
        A[i] = query(p[i]);
        B[i] = p[i] - 1 - A[i];
        add(p[i]);
        sum += min(A[i],B[i]);
        xx.add(i,p[i]),yy.add(i,p[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(A[i]==B[i]) t1.add(i,p[i]);
        if(A[i] + 1 == B[i]) t2.add(i,p[i]);
        if(A[i]==B[i] + 1) t3.add(i,p[i]);
        if(A[i] + 2 <= B[i]) t4.add(i,p[i]);
        if(B[i] + 2 <= A[i]) t5.add(i,p[i]);
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i];
        if(x[i]>y[i]) swap(x[i],y[i]);
        int L = x[i] + 1,R = y[i] - 1;
        int low = min(p[x[i]],p[y[i]]),high = max(p[x[i]],p[y[i]]);
        t1.que(L,low,R,high,i);
        t2.que(L,low,R,high,i);
        t3.que(L,low,R,high,i);
        t4.que(L,low,R,high,i);
        t5.que(L,low,R,high,i);
        xx.que(x[i],1,y[i],p[x[i]]-1,i);
        yy.que(x[i],1,y[i],p[y[i]]-1,i);
    }
    t1.get(ans1);
    t2.get(ans2);
    t3.get(ans3);
    t4.get(ans4);
    t5.get(ans5);
    xx.get(ansxx);
    yy.get(ansyy);
    for(int i=1;i<=m;i++){
        if(p[x[i]]<p[y[i]]) ans[i] += sum - ans1[i] - ans2[i] - ans4[i] + ans5[i];
        else ans[i] += sum - ans1[i] - ans3[i] + ans4[i] - ans5[i];
        ans[i] -= min(A[x[i]],B[x[i]]),ans[i] -= min(A[y[i]],B[y[i]]);
        ans[i] += min(A[x[i]] + ansxx[i],B[x[i]] - ansxx[i]),ans[i] += min(A[y[i]] - ansyy[i],B[y[i]] + ansyy[i]);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}

原文地址：http://www.cnblogs.com/aitejiu/p/16875516.html