自助建站凡科网,古典lash网站带后台源码下载,江苏百度推广代理商,淮北建站题目描述 我早已习惯你不在身边#xff0c;人间四月天 寂寞断了弦。回望身后蓝天#xff0c;跟再见说再见……某天,蒟蒻Autumn发现了从 Gty的妹子树(bzoj3720) 上掉落下来了许多妹子,他发现她们排成了一个序列,每个妹子有一个美丽度。Bakser神犇与他打算研究一下这个妹子序列…题目描述 我早已习惯你不在身边 人间四月天 寂寞断了弦。 回望身后蓝天 跟再见说再见…… 某天,蒟蒻Autumn发现了从 Gty的妹子树(bzoj3720) 上掉落下来了许多妹子,他发现 她们排成了一个序列,每个妹子有一个美丽度。 Bakser神犇与他打算研究一下这个妹子序列,于是Bakser神犇问道:你知道区间 [l,r]中妹子们美丽度的逆序对数吗? 蒟蒻Autumn只会离线乱搞啊……但是Bakser神犇说道:强制在线。 请你帮助一下Autumn吧。 给定一个正整数序列a,对于每次询问,输出al...ar中的逆序对数,强制在线。 输入 第一行包括一个整数n(1n50000),表示数列a中的元素数。 第二行包括n个整数a1...an(ai0,保证ai在int内)。 接下来一行包括一个整数m(1m50000),表示询问的个数。 接下来m行,每行包括2个整数l、r(1lrn),表示询问al...ar中的逆序对数(若aiaj且ij,则为一个逆序对)。 l,r要分别异或上一次询问的答案(lastans),最开始时lastans0。保证涉及的所有数在int内。 输出 对每个询问,单独输出一行,表示al...ar中的逆序对数。 样例输入 4 1 4 2 3 1 2 4 样例输出 2 题解 分块树状数组主席树 由于题目强制在线所以不能离线乱搞了。 正常来说在线查询区间内比某数大/小的数的个数使用的数据结构是主席树。 然而这样依然要查询询问区间内每个元素这样时间复杂度还是不能下降。 我们想到可以使用分块预处理查询时只查询块外元素能够使时间复杂度降低。 具体地设f[i][j]表示从第i块开始到第j个位置结束的逆序对数。这样枚举每个i就能够在$O(n\log n)$的时间内预处理。 对于每个查询找到查询区间内第一个整块根据f数组得到它到区间右端的逆序对数这样剩下的就只有区间左端块外元素使用主席树查询即可。 总时间复杂度为$O((nm)\sqrt n\log n)$另外听大爷说本题卡常所以在预处理时需要使用树状数组。 #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;
}转载于:https://www.cnblogs.com/GXZlegend/p/7071469.html
