Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

生活中，大多数事物都是有序的，因为顺序的美是最令人陶醉的。所以现在RCDH看了不顺的东西就头痛。所以他想让世界变成有序，

可是他只是一个无名小辈，所以只好对数字序列下手。据他所知序列的混乱程度是由“逆序对”的个数决定，公式是Q=2^n,其中

Q是指混乱程度，n是指这个序列“逆序对”的个数。逆序对是这样定义的：假设序列中第I个数是ai，若存在Iaj，则

就为一个逆序对。你的任务是给定一个序列，计算其混乱程度Q。这个数可能会比较大，你只需输出Q mod 1991 的结果。

【输入格式】

第一行，整数n，表示序列中有n个数。

第二行，有n个数。

【输出格式】

仅一行，Q mod 1991 的值。

样例注释：样例中共有2个逆序对，故Q=2^2=4。所以，Q mod 1991=4。

【数据规模】

对于30%的数据 2= 对于100%的数据 2= 数列中的每个数不超过10000000的正整数。

Sample Input

4

1 3 4 2

Sample Output

4

【题目链接】:

【题意】

【题解】

线段树求逆序对的方法:

这里有会有重复数字,求逆序对的时候注意先递增相同大小的数字的答案,再更新线段树

【完整代码】

//n最大5万#include 
     
      #include 
      
       #include 
       
        using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%lld",&x)#define ref(x) scanf("%lf",&x)typedef pair
        
          pii;typedef pair
         
           pll;const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };const double pi = acos(-1.0);const int N = 5e4+100;const LL mod = 1991;struct abc{    int x, id;};int n;LL sum[N << 2];LL ni = 0,temp = 1;abc a[N];bool cmp1(abc a, abc b){    return a.x > b.x;}void in(){    rei(n);    rep1(i, 1, n)        rei(a[i].x), a[i].id = i;}void up_data(int pos,int l, int r, int rt){    if (l == r)    {        sum[rt]++;        return;    }    int m = (l + r) >> 1;    if (pos <= m)        up_data(pos, lson);    else        up_data(pos, rson);    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}LL query(int L, int R, int l, int r, int rt){    if (L > R)        return 0;    if (L <= l && r <= R)        return sum[rt];    int m = (l + r) >> 1;    LL temp1 = 0, temp2 = 0;    if (L <= m)        temp1 += query(L, R, lson);    if (m < R)        temp2 += query(L, R, rson);    return temp1 + temp2;}void get_ans(){    rep1(i, 1, n)    {        int l = i,r = i;        while (r + 1 <= n && a[r + 1].x == a[l].x) r++;        rep1(j, l, r)            ni += query(1, a[j].id - 1, 1, n, 1);        rep1(j,l,r)            up_data(a[j].id, 1, n, 1);        i = r;    }}void ksm(LL x){    if (!x) return;    ksm(x >> 1);    temp = (temp*temp) % mod;    if (x & 1)        temp = (temp * 2) % mod;}void o(){    printf("%I64d\n", temp);}int main(){    //freopen("F:\\rush.txt", "r", stdin);    in();    sort(a + 1, a + 1 + n, cmp1);    get_ans();    ksm(ni);    o();    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);    return 0;}