BZOJ 3289 Mato的文件管理 (莫队算法套树状数组)
http://www.lydsy.com/JudgeOnline/problem.php?id=3289
题意：中文题目，简单来说就是求某一区间内的逆序对数。
思路：逆序对数想到树状数组。不过写莫队转移的时候没弄明白。。。。大概是树状数组理解的还不够透彻。。。需要复习一下了。。。
还有这题没给数据范围但是需要离散化。。。不然会re...
/* ***********************************************
Author :111qqz
Created Time :2016年02月17日 星期三 20时18分51秒
File Name :code/bzoj/3289.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=5E4+11;
7int n,m;
8int a[N],b[N];
9int pos[N];
10LL c[N];
11LL ans[N];
12LL sum;
13struct node
14{
15 int l,r;
16 int id;
1 bool operator < (node b)const
2 {
3 if (pos[l]==pos[b.l]) return r<b.r;
4 return pos[l]<pos[b.l];
5 }
6}q[N];
1int lowbit( int x)
2{
3 return x&(-x);
4}
1void update ( int x,int delta)
2{
3 for ( int i = x ;i <=n ; i+=lowbit(i))
4 {
5 c[i] +=delta;
6 }
7}
1LL Sum( int x)
2{
3 LL res = 0LL ;
4 for ( int i = x; i >=1 ; i-=lowbit(i))
5 {
6 res += 1LL*c[i];
7 }
8 return res;
9}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("code/in.txt","r",stdin);
5 #endif
1 scanf("%d",&n);
2 int siz = 223; //sqrt(50000);
3 for ( int i = 1 ;i <= n ; i++)
4 {
5 scanf("%d",&a[i]);
6 pos[i] = (i-1)/siz;
7 b[i] = a[i];
8 }
9 sort(b+1,b+n+1);
10 int t = unique(b+1,b+n+1)-b-1;
11 for ( int i = 1 ; i <= n ; i++) a[i] = lower_bound(b+1,b+t+1,a[i])-b;
1// for ( int i = 1 ;i <= n ; i++) cout<<"a[i]:"<<a[i]<<endl;
2 scanf("%d",&m);
3 for ( int i = 1 ;i <= m; i++)
4 {
5 scanf("%d %d",&q[i].l,&q[i].r);
6 q[i].id = i ;
7 }
sort(q+1,q+m+1);
1 int pl=1,pr=0;
2 int l,r,id;
3 sum = 0 ;
4 ms(c,0);
5 ms(ans,0LL);
6 for ( int i = 1; i <= m; i++)
7 {
8 l = q[i].l;
9 r = q[i].r;
10 id = q[i].id;
11 while (pr<r)
12 {
13 update(a[++pr],1);
14 sum +=pr-pl-Sum(a[pr]-1);
15 }
16 while (pr>r)
17 {
18 sum -= pr-pl-Sum(a[pr]-1);
19 update(a[pr--],-1);
20 }
21 while (pl<l)
22 {
23 sum -= Sum(a[pl]-1);
24 update(a[pl++],-1);
25 }
26 while (pl>l)
27 {
28 update(a[--pl],1);
29 sum +=Sum(a[pl]-1);
30 }
// cout<<"sum:"<<sum<<endl;
1 ans[id] = sum;
2 }
3 for ( int i = 1 ; i <= m ; i++) printf("%lld\n",ans[i]);
4 #ifndef ONLINE_JUDGE
5 fclose(stdin);
6 #endif
7 return 0;
8}