BZOJ 3289 Mato的文件管理 (莫队算法套树状数组)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年02月17日 星期三 20时18分51秒
  4File Name :code/bzoj/3289.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=5E4+11;
 34int n,m;
 35int a[N],b[N];
 36int pos[N];
 37LL c[N];
 38LL ans[N];
 39LL sum;
 40struct node
 41{
 42    int l,r;
 43    int id;
 44
 45    bool operator < (node b)const
 46    {
 47	if (pos[l]==pos[b.l]) return r<b.r;
 48	return pos[l]<pos[b.l];
 49    }
 50}q[N];
 51
 52int lowbit( int x)
 53{
 54    return x&(-x);
 55}
 56
 57void update ( int x,int delta)
 58{
 59    for ( int i = x ;i <=n ; i+=lowbit(i))
 60    {
 61	c[i] +=delta;
 62    }
 63}
 64
 65LL Sum( int x)
 66{
 67    LL res = 0LL ;
 68    for ( int i = x; i >=1 ; i-=lowbit(i))
 69    {
 70	res += 1LL*c[i];
 71    }
 72    return res;
 73}
 74
 75
 76int main()
 77{
 78	#ifndef  ONLINE_JUDGE 
 79	freopen("code/in.txt","r",stdin);
 80  #endif
 81
 82	scanf("%d",&n);
 83	int siz = 223; //sqrt(50000);
 84  	for ( int i = 1 ;i  <= n ; i++)
 85 	{
 86	    scanf("%d",&a[i]);
 87	    pos[i] = (i-1)/siz;
 88	    b[i] = a[i];
 89	}
 90	 sort(b+1,b+n+1);
 91	 int t = unique(b+1,b+n+1)-b-1;
 92	 for ( int i = 1 ; i <= n ; i++) a[i] = lower_bound(b+1,b+t+1,a[i])-b;
 93
 94//	 for ( int i = 1 ;i <= n ; i++) cout<<"a[i]:"<<a[i]<<endl;
 95	 scanf("%d",&m);
 96	 for ( int i = 1 ;i  <= m;  i++)
 97	 {
 98	     scanf("%d %d",&q[i].l,&q[i].r);
 99	     q[i].id = i ;
100	 }
101
102	 sort(q+1,q+m+1);
103
104	 int pl=1,pr=0;
105	 int l,r,id;
106	 sum = 0 ;
107	 ms(c,0);
108	 ms(ans,0LL);
109	 for ( int i = 1; i <= m; i++)
110	 {
111	     l = q[i].l;
112	     r = q[i].r;
113	     id = q[i].id;
114	     while (pr<r)
115	    {
116		update(a[++pr],1);
117		sum +=pr-pl-Sum(a[pr]-1);
118	    }
119	     while (pr>r)
120	     {
121		 sum -= pr-pl-Sum(a[pr]-1);
122		 update(a[pr--],-1);
123	     }
124	     while (pl<l)
125	     {
126		 sum -= Sum(a[pl]-1);
127		 update(a[pl++],-1);
128	     }
129	     while (pl>l)
130	     {
131		 update(a[--pl],1);
132		 sum +=Sum(a[pl]-1);
133	     }
134
135	//     cout<<"sum:"<<sum<<endl;
136
137	     ans[id] = sum;
138	 }
139	 for ( int i = 1 ; i <= m ; i++) printf("%lld\n",ans[i]);
140  #ifndef ONLINE_JUDGE  
141  fclose(stdin);
142  #endif
143    return 0;
144}