莫队维护逆序对，区间左右增减要分类讨论。

 

记得离散化。

 

1 /**************************************************************  2     Problem: 3289  3     User: idy002  4     Language: C++  5     Result: Accepted  6     Time:5480 ms  7     Memory:3164 kb  8 ****************************************************************/  9   10 #include 
      
        11 #include 
       
         12 #include 
        
          13 #include 
         
           14 #define maxn 50010 15 #define lowbit(i) ((i)&(-(i))) 16 using namespace std; 17   18 typedef long long lng; 19   20 int n, m; 21 int disc[maxn]; 22 int lx[maxn], rx[maxn], mccno[maxn], stot; 23 int w[maxn]; 24 lng cnt[maxn], cnttot, cur_ans; 25 lng ans[maxn]; 26   27 struct Qu { 28     int l, r, id; 29     bool operator<( const Qu & b ) const { 30         return mccno[l]
          
           qu[q].l ) push_front( w[--lf] ); 92         while( rg
           
            qu[q].r ) pop_back( w[rg--] ); 94 ans[qu[q].id] = cur_ans; 95 } 96 } 97 int main() { 98 scanf( "%d", &n ); 99 for( int i=1; i<=n; i++ ) {100 scanf( "%d", w+i );101 disc[i] = w[i];102 }103 sort( disc+1, disc+1+n );104 for( int i=1; i<=n; i++ )105 w[i] = lower_bound( disc+1, disc+1+n, w[i] ) - disc;106 scanf( "%d", &m );107 for( int i=1; i<=m; i++ ) {108 scanf( "%d%d", &qu[i].l, &qu[i].r );109 qu[i].id = i;110 }111 partition();112 work();113 for( int i=1; i<=m; i++ ) 114 printf( "%lld\n", ans[i] );115 }