OJ周赛第二场——逆序对

标签：周赛 OJ 10 int 序列 操作 pn 逆序

逆序对  

问题描述 

给你一个长度为n的排列的置换p

(长度为n的排列的置换的定义为：对于排列1，2，3....n,你可以多次交换两个数后的序列。比如（1，5，4，2，3）是一个排列的置换，（3，2，4，2，1）则不是，因为2出现了两次并且5没有出现)

对于序列p{p1,p2,p3,…,pn}有两个操作需要你进行。

1.后置，将序列P的首项放到P的末尾，操作后p′={p2,p3,…,pn,p1}

2.翻转，将序列整个翻转，操作后 p′={pn,pn−1,…,p2,p1}

对于每次操作后，你需要求出操作后序列的逆序对个数。（逆序对的个数为对于序列p,有i<j,pi>pj的个数）

 

输入

第一行给定两个整数n,m (1≤n≤3×10^5,1≤m≤6×10^5) 表示给定序列的长度和操作的次数。

第二行给定n个整数的序列p (1≤pi≤n)。给定的pi保证不会重复。

第三行一个长度为m的字符串。该串有'R'和'S'组成，'R'表示操作2翻转，'S'表示操作1后置 

输出 

输出一行m个数，表示进行第i个操作后的逆序对个数对10取模。具体请看样例。

 

输入例子 1 

5 10
5 4 3 2 1
SSSSRSSSSR

输出例子 1

6446466400

 

提示

原序列的逆序对数为10

第一个操作后为（4，3，2，1，5），逆序对为6，输出6

第二个操作后为（3，2，1，5，4），逆序对为4，输出4

以下同理

 

先求出序列的逆序对，可以通过树状数组或分治求，方法很多。

考虑单独的两个操作

操作1，如果队列第一个为x，那么把他放到最后，我们可以发现，这样原序列后面比他小的数就无法和他形成逆序对，放到后面后会和比他大的数产生逆序对。那么变化为+（x-1）-（n-x）

操作2，原序列为x，那么翻转就是n*（n-1）/2 -x；即全部的减去原来的。

那么如果翻转后再进行操作1，就是相当于把最后一个插到前面，即-（x-1）+（n-x）

 

答案：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int f[N];
int n,m;
void add(int x){
    for (;x<=n;x+=x&-x) f[x]++;
}
int sum(int x){
    int s=0;
    for (;x;x-=x&-x) s+=f[x];
    return s;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    
    string s;
    cin>>n>>m;
    
    deque<int> p;
    long long s1=0,all=1LL*n*(n-1)/2;
    for (int i=1;i<=n;++i){
        int x;cin>>x;
        p.push_back(x);
        s1+=sum(n-x);
        add(n-x+1);
    }  // 求p的逆序对
    
    cin>>s;
    
    
    string ans;
    int rev=0;
    for (int i=0;i<m;++i){
        if (s[i]=='S'){
            int x;
            if (rev){
                x=p.back();
                s1=s1 -  (n-x) + (x-1);
                p.pop_back();
                p.push_front(x);
                ans+=char( (all-s1)%10 + '0');
            }else{
                x=p.front();
                s1=s1+ (n-x) - (x-1);
                p.pop_front();
                p.push_back(x);
                ans+=char( s1%10 + '0');
            }
        }else {
            rev^=1;
            if (rev) ans+=char( (all-s1)%10 + '0');
             else     ans+=char( s1%10 + '0');
        }
    }
    
    cout<<ans;
}

 

标签：周赛,OJ,10,int,序列,操作,pn,逆序
From： https://www.cnblogs.com/hihopkc/p/16866118.html