emmm

显然的考虑影响

后面比x小的

前面比x大的

还要单点修改

只有树套树了。

 

暴力无脑线段树套fhq 会TLE到80pts

单点修改，区间查询

树状数组套动态开点线段树显然更优啊

2781ms

// luogu-judger-enable-o2#include
     
      #define il inline#define reg register int#define numb (ch^'0')#define mid ((l+r)>>1)using namespace std;typedef long long ll;il void rd(int &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=100000+5;int n,m;int a[N];int p[N];int b[N];struct arraytree{    int f[N];    void add(int x){        for(;x<=n;x+=x&(-x)) ++f[x];    }    int query(int x){        int ret=0;        for(;x;x-=x&(-x)) ret+=f[x];        return ret;        }}at;struct node{    int ls,rs;    int sz;}t[N*200];int tot;int rt[N];void upda(int &x,int l,int r,int p,int c){//    cout<<" upda "<
      
       <<" "<
       
        <<" to "<
        
<<" and "<
         
          <
          
           r) return 0; int ret=0; for(;x;x-=x&(-x)){ ret+=query(rt[x],1,n,l,r); } return ret;}void dele(int x){ int pos=p[x]; for(;pos<=n;pos+=pos&(-pos)){ upda(rt[pos],1,n,x,-1); }}int main(){ rd(n);rd(m); ll ans=0; for(reg i=1;i<=n;++i) { rd(a[i]); b[i]=a[i]; p[a[i]]=i; } for(reg i=n;i>=1;--i){ ans+=at.query(a[i]-1); at.add(a[i]); } int x; printf("%lld\n",ans); build();// cout<<" after build-----------------------------------"<