# 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