当前位置:网站首页>Bzoj3289: file management of Mato (Mo team + tree array)

Bzoj3289: file management of Mato (Mo team + tree array)

2020-12-07 15:04:42 osc_ 1m04dwae

Subject portal
.

solution :
I just saw Gty The sister sequence of . All kinds of things don't ..
See this question ..
Don't force online ?
Mo team .
It's good to find the reverse order of the tree array .




If you think it's very complicated, you'll run very slowly 5s It's over ...

Code implementation :

#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;
}

版权声明
本文为[osc_ 1m04dwae]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/202012071504368588.html