CTSC2008totem [WC2016 simulation] Picture

Description


(2)

Input

Output

Sample Input

Sample input 1:
5
1 5 3 2 4
Sample input 2:
4
1 2 4 3

Sample Output

Sample output 1:
0
Sample output 2:
16777215

Data Constraint

The question is
1324-1432-1243
=(1x2x-1423)-(14xx-1423)-(12xx-1234)
=1x2x-14xx-12xx+1234
=1x2x+1234+13xx-1xxx

Discuss them separately~

Let li[i] be the number of points in the lower left corner of I, and ri[i] be the lower right corner
1xxx: simple
1234: enumeration 3, "12" (n − I − ri[i]) * Σ J < I, a [J] < a [i] Li [J], implemented by line tree
13xx: enumerating 3, we find that what we need is (1,3,2)*(n-i-ri[i]), because 4 is legal no matter in the middle of 3,2 or on the far right
For J < I, x < a [i], y < a [i], there are li[i]* (a[i]-1) filling methods
But there are two more cases
1: K < I and Y > x, a kind of multi calculation, li[i]*(li[i]-1)/2
2: Y < = x, a [J] < a [i] a [J]

1x2x: enum 2
What we find is (1,3,2)*(n-i-ri[i])
There are li[i]*(i-1) filling methods for J < I, a [J] < a [i] K < I
It's the same in two cases
1: In the case of K < J, Σ J < I, a [J] < a [i] J is calculated
2: In the case of k > = J and K < a [i], li[i]*(li[i]-1)/2 (in fact, 0 + 1 + +(li[i]-1))

Paste code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define ll long long

using namespace std;

const int maxn=2e5+5,md=16777216;

int tree[maxn*3];
int i,j,k,l,m,n,x,y,p;
int a[maxn];
ll li[maxn],ri[maxn];
ll z,ans,c;

void find(int v,int l,int r,int x,int y){
    if (l==x && r==y) z=z+tree[v]; else{
        int mid=(l+r)/2;
        if (y<=mid) find(v*2,l,mid,x,y); else
        if (x>mid) find(v*2+1,mid+1,r,x,y); else{
            find(v*2,l,mid,x,mid);
            find(v*2+1,mid+1,r,mid+1,y);
        }
    }
}
void change(int v,int l,int r,int x){
    if (l==r){
        tree[v]=tree[v]+p;
        return;
    }
    int mid=(l+r)/2;
    if (x<=mid) change(v*2,l,mid,x); else change(v*2+1,mid+1,r,x);
    tree[v]=tree[v*2]+tree[v*2+1];
}
int main(){
//  freopen("t3.in","r",stdin);
    scanf("%d",&n); p=1;
    fo(i,1,n){
        scanf("%d",&a[i]); z=0;
        find(1,1,n,1,a[i]); li[i]=z; ri[i]=a[i]-li[i]-1;
        change(1,1,n,a[i]);
    }
    memset(tree,0,sizeof(tree));
    fo(i,1,n){
        z=0; find(1,1,n,1,a[i]);
        c=n-i-ri[i];
        ans=(ans+z*c)%md;
        if (c>2){
            z=(((c*(c-1))/2*(c-2))/3)%md;
            ans=(ans-z+md)%md;
        }
        p=li[i]; change(1,1,n,a[i]);
    }
    memset(tree,0,sizeof(tree));
    fo(i,1,n){
        z=0; find(1,1,n,1,a[i]);
        if (li[i])
        z=(md+(md-z)%md+(li[i]*(i-1)-((li[i]*(li[i]-1))/2)%md)%md)%md;
        z=(z*(n-i-ri[i]))%md;
        ans=(ans+z)%md;
        p=i; change(1,1,n,a[i]);
    }
    memset(tree,0,sizeof(tree));
    fo(i,1,n){
        z=0; find(1,1,n,1,a[i]);
        if (li[i])
        z=(md+(md-z)%md+(li[i]*(a[i]-1)-((li[i]*(li[i]-1))/2)%md)%md)%md;
        z=(z*(n-i-ri[i]))%md; ans=(ans+z)%md;
        p=a[i]; change(1,1,n,a[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

Posted on Mon, 04 May 2020 19:20:13 -0700 by soupy127