bzoj3289: Mato的文件管理（莫队+树状数组）

2020-12-07 15:04:42

``````#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
struct node {

int l,r,id,ans;}a[51000];int sum[51000],n,f[51000],s[51000];
bool cmp(node n1,node n2) {

if(f[n1.l]==f[n2.l])return n1.r<n2.r;return n1.l<n2.l;}
int lowbit(int x) {

return x&-x;}
void change(int x) {

while(x<=n) {sum[x]++;x+=lowbit(x);}}
void _change(int x) {

while(x<=n) {sum[x]--;x+=lowbit(x);}}
int find_sum(int x) {

int ans=0;while(x>0) {ans+=sum[x];x-=lowbit(x);}return ans;}
struct lsnode {

int x,id;}b[51000];
bool cmp1(lsnode n1,lsnode n2) {

return n1.x<n2.x;}
bool cmp2(node n1,node n2) {

return n1.id<n2.id;}
int main() {
scanf("%d",&n);int unit=int(sqrt(double(n+1)));
for(int i=1;i<=n;i++) {

scanf("%d",&b[i].x);b[i].id=i;f[i]=i/unit+1;}
sort(b+1,b+1+n,cmp1);int tot=0;b[0].x=0;
for(int i=1;i<=n;i++) {

if(b[i].x!=b[i-1].x)tot++;s[b[i].id]=tot;}
memset(sum,0,sizeof(sum));int m;scanf("%d",&m);
for(int i=1;i<=m;i++) {

scanf("%d%d",&a[i].l,&a[i].r);a[i].id=i;}
sort(a+1,a+1+m,cmp);int ans=0;
for(int i=a[1].r;i>=a[1].l;i--) {ans+=find_sum(s[i]-1);change(s[i]);}
int l=a[1].l,r=a[1].r;a[1].ans=ans;
for(int i=2;i<=m;i++) {
while(l<a[i].l) {
int x=s[l];l++;
ans-=find_sum(x-1);
_change(x);
}
while(l>a[i].l) {
l--;int x=s[l];
ans+=find_sum(x-1);
change(x);
}
while(r<a[i].r) {
r++;int x=s[r];
ans+=(r-l)-find_sum(x);change(x);
}
while(r>a[i].r) {
int x=s[r];
ans-=(r-l+1)-find_sum(x);_change(x);r--;
}a[i].ans=ans;
}sort(a+1,a+1+m,cmp2);
for(int i=1;i<=m;i++)printf("%d\n",a[i].ans);
return 0;
}``````

https://my.oschina.net/u/4412764/blog/4778743