題目描述

我早已習(xí)慣你不在身邊， 人間四月天 寂寞斷了弦。 回望身后藍天， 跟再見說再見…… 某天,蒟蒻Autumn發(fā)現(xiàn)了從 Gty的妹子樹(bzoj3720) 上掉落下來了許多妹子,他發(fā)現(xiàn) 她們排成了一個序列,每個妹子有一個美麗度。 Bakser神犇與他打算研究一下這個妹子序列,于是Bakser神犇問道:"你知道區(qū)間 [l,r]中妹子們美麗度的逆序?qū)?shù)嗎?" 蒟蒻Autumn只會離線亂搞啊……但是Bakser神犇說道:"強制在線。" 請你幫助一下Autumn吧。 給定一個正整數(shù)序列a,對于每次詢問,輸出al...ar中的逆序?qū)?shù),強制在線。

輸入

第一行包括一個整數(shù)n(1<=n<=50000),表示數(shù)列a中的元素數(shù)。 第二行包括n個整數(shù)a1...an(ai>0,保證ai在int內(nèi))。 接下來一行包括一個整數(shù)m(1<=m<=50000),表示詢問的個數(shù)。 接下來m行,每行包括2個整數(shù)l、r(1<=l<=r<=n),表示詢問al...ar中的逆序?qū)?shù)(若ai>aj且i<j,則為一個逆序?qū)?。 l,r要分別異或上一次詢問的答案(lastans),最開始時lastans=0。保證涉及的所有數(shù)在int內(nèi)。

輸出

對每個詢問,單獨輸出一行,表示al...ar中的逆序?qū)?shù)。

樣例輸入

4
1 4 2 3
1
2 4

樣例輸出

2

---

題解

分塊+樹狀數(shù)組+主席樹

由于題目強制在線，所以不能離線亂搞了。

正常來說，在線查詢區(qū)間內(nèi)比某數(shù)大/小的數(shù)的個數(shù)，使用的數(shù)據(jù)結(jié)構(gòu)是主席樹。

然而這樣依然要查詢詢問區(qū)間內(nèi)每個元素，這樣時間復(fù)雜度還是不能下降。

我們想到可以使用分塊預(yù)處理，查詢時只查詢塊外元素，能夠使時間復(fù)雜度降低。

具體地，設(shè)f[i][j]表示從第i塊開始，到第j個位置結(jié)束的逆序?qū)?shù)。這樣枚舉每個i，就能夠在$O(n\log n)$的時間內(nèi)預(yù)處理。

對于每個查詢，找到查詢區(qū)間內(nèi)第一個整塊，根據(jù)f數(shù)組得到它到區(qū)間右端的逆序?qū)?shù)，這樣剩下的就只有區(qū)間左端塊外元素，使用主席樹查詢即可。

總時間復(fù)雜度為$O((n+m)\sqrt n\log n)$，另外聽大爺說本題卡常，所以在預(yù)處理時需要使用樹狀數(shù)組。

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define N 100010 using namespace std; int a[N] , v[N] , sum[250][N] , f[N] , n , ls[N << 4] , rs[N << 4] , si[N << 4] , root[N] , tot; void update(int x) {int i;for(i = x ; i <= n ; i += i & -i) f[i] ++ ; } int query(int x) {int i , ans = 0;for(i = x; i ; i -= i & -i) ans += f[i];return ans; } void insert(int p , int l , int r , int x , int &y) {y = ++tot , si[y] = si[x] + 1;if(l == r) return;int mid = (l + r) >> 1;if(p <= mid) rs[y] = rs[x] , insert(p , l , mid , ls[x] , ls[y]);else ls[y] = ls[x] , insert(p , mid + 1 , r , rs[x] , rs[y]); } int calc(int p , int l , int r , int x , int y) {if(l > p) return 0;if(r <= p) return si[y] - si[x];int mid = (l + r) >> 1;return calc(p , l , mid , ls[x] , ls[y]) + calc(p , mid + 1 , r , rs[x] , rs[y]); } int main() {int m , i , j , si , last = 0 , x , y , ans;scanf("%d" , &n) , si = (int)sqrt(n);for(i = 0 ; i < n ; i ++ ) scanf("%d" , &a[i]) , v[i] = a[i];sort(v , v + n);for(i = 0 ; i < n ; i ++ ) a[i] = lower_bound(v , v + n , a[i]) - v , insert(a[i] , 0 , n - 1 , root[i] , root[i + 1]);for(i = 0 ; i <= n / si ; i ++ ){memset(f , 0 , sizeof(f)) , update(n - a[i * si]);for(j = i * si + 1 ; j < n ; j ++ ) sum[i][j] = sum[i][j - 1] + query(n - a[j] - 1) , update(n - a[j]);}scanf("%d" , &m);while(m -- ){scanf("%d%d" , &x , &y) , x = (x ^ last) - 1 , y = (y ^ last) - 1 , ans = 0;if(x / si == y / si)for(i = y - 1 ; i >= x ; i -- )ans += calc(a[i] - 1 , 0 , n - 1 , root[i + 1] , root[y + 1]);else{ans += sum[x / si + 1][y];for(i = (x / si + 1) * si - 1 ; i >= x ; i -- )ans += calc(a[i] - 1 , 0 , n - 1 , root[i + 1] , root[y + 1]);}printf("%d\n" , last = ans);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/7071469.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj3744】Gty的妹子序列 分块+树状数组+主席树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。