白手 @ 2020-09-28 17:25:07
#include<bits/stdc++.h>
#define INF 2147483647
#define ll long long
using namespace std;
const int Max=5e5+20;
const int Maxn=5e6+20;
const int mod=10007;
inline int read()
{
int f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return x*f;
}
struct edgu
{
ll v,lr,rr;
}tree[Maxn];
int cnt=1;
ll search_tree(int l,int L,int R,int nood)
{
if(nood==0) return 0;
if(L>R) return 0;
if(l<=L) return tree[nood].v;
int mid=(L+R)>>1;
ll num=0;
if(l<=mid) num+=search_tree(l,L,mid,tree[nood].lr);
num+=search_tree(l,mid+1,R,tree[nood].rr);
return num;
}
void insert_tree(int pos,int l,int r,int nood)
{
if(l==r) {tree[nood].v++;return;}
if(l>r) return;
int mid=(l+r)>>1;
if(pos<=mid)
{
if(tree[nood].lr==0) tree[nood].lr=++cnt;
insert_tree(pos,l,mid,tree[nood].lr);
}
else
{
if(tree[nood].rr==0) tree[nood].rr=++cnt;
insert_tree(pos,mid+1,r,tree[nood].rr);
}
tree[nood].v=tree[tree[nood].lr].v+tree[tree[nood].rr].v;
}
int main()
{
int n=read(),a;
ll ans=0;
for(int i=1;i<=n;i++)
{
a=read();
ans+=search_tree(a+1,1,1000000000,1);
insert_tree(a,1,1000000000,1);
}
cout<<ans<<endl;
}
by fresh_boy @ 2020-09-28 17:39:52
废话,相当于你存了3个
by xiejinhao @ 2020-09-28 18:11:07
明明可以归并或者树状数组,为啥用线段树?
再说了
by xiejinhao @ 2020-09-28 18:12:33
@白手
by 白手 @ 2020-09-28 18:48:11
@xiejinhao 都试试嘛,改int过了
by 白手 @ 2020-09-28 18:49:24
@xiejinhao 这是动态开点,是能存下的哦