Mato的文件管理 （莫队）题解

思路：

莫队模板题，转换几次就是找逆序数，用树状数组来储存数就行了

注意要离散化

代码：

#include<queue> #include<cstring> #include<set> #include<map> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<iostream> #include<algorithm> #define ll long long const int N = 50000+5; using namespace std; int k[N],p[N],arr[N],pos[N],ans[N],n,m; struct node{int l,r;int id; }e[N]; bool cmp(node a,node b){return pos[a.l] == pos[b.l]? a.r < b.r : pos[a.l] < pos[b.l];} int lowbit(int x){return x&(-x); } void update(int x,int val){for(int i = x;i <= n;i += lowbit(i))arr[i] += val; } int sum(int x){int ret = 0;for(int i = x;i > 0;i -= lowbit(i)){ret += arr[i];}return ret; } void Do(){//i位置 //L右移，逆序对数减少p[i]的逆序数 //L左移，逆序对数增加p[i-1]的逆序数 //R右移，逆序对数增加大于p[i+1]的数 //R左移，逆序对数减少大于p[i]的数 int L = 1,R = 0;int ret = 0;for(int i = 1;i <= m;i++){while(L < e[i].l){update(p[L],-1);ret -= sum(p[L] - 1);L++;}while(L > e[i].l){L--;update(p[L],1);ret += sum(p[L] - 1);}while(R < e[i].r){R++;update(p[R],1);ret += R - L + 1 - sum(p[R]); //大于减去自己和比己小的 }while(R > e[i].r){update(p[R],-1);ret -= R - L -sum(p[R]);R--;}ans[e[i].id] = ret;} } int main(){scanf("%d",&n);int block = sqrt(n);for(int i = 1;i <= n;i++){scanf("%d",&p[i]);k[i] = p[i];pos[i] = (i - 1) / block + 1;}sort(k+1,k+n+1);for(int i = 1;i <= n;i++) p[i] = lower_bound(k+1,k+n+1,p[i]) - k;scanf("%d",&m);for(int i = 1;i <= m;i++){scanf("%d%d",&e[i].l,&e[i].r);e[i].id = i;}sort(e+1,e+m+1,cmp); //分块 Do();for(int i =1;i <= m;i++)printf("%d\n",ans[i]);return 0; }

转载于:https://www.cnblogs.com/KirinSB/p/9408798.html

总结

以上是生活随笔为你收集整理的Mato的文件管理 （莫队）题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。