P6774 [noi2020] tears in the era (block)

Preface

See the title ： Don't scold. Don't scold .

A very regular YNOI Well .
Stuck in the contribution of the whole block to the whole block .
This is really the worst part of the problem .

Pre knowledge ：Yuno loves sqrt technology I

analysis

Interval reverse pair enhanced version ？ It's hard not to think of two YLST.
However, there are two-dimensional restrictions , Erli seems to have no future .
Consider the block online approach .

Set the inquiry range to $[l,r]$, The range of values is $[bot,top]$.
It's still the old way , Divide the contribution into pieces 、 Inside the whole block 、 Pieces to pieces 、 One piece to one piece 、 The five parts of the whole block , And the situation in the same block .

Inside the bulk ：.… How to do this At this time, it is inevitable to have the impulse to go up the tree array . But a little thought can find , The value in each block is only $O(\sqrt{n})$ individual , So you might as well preprocess it directly The ranking of each number in the block as well as The prefix and... Of the ranking within each block , Then it's just a direct differential check .
Pieces to pieces ： Old ways , Merge and sort .
One piece to one piece ： A more intuitive idea is to exclude , Find out $[1,top]$ The answer , subtracting $[1,bot-1]$ The answer , Then subtract $[1,bot-1]$ The number of $[bot,top]$ The contribution made .
Finally, the reduced contribution is easy to solve with prefix and make a mess , So how to find out the value range between the whole block, such as $[1,x]$ The answer is ？（ I'm stuck here ）
The answer is shaped like ${\sum }_b{\sum }_{a<b}ans(a,b,1,x)$, Consider converting to all $b$ Find out all ${\sum }_{a<b}ans(a,b,1,x)$ Then sum it .
Then the form of this seems to be very easy , It's enumeration $b$ All in the block are $[1,x]$ Check the order of the elements in the front, and then preprocess it .
Pieces to pieces ： Enumerate chunked elements , Prefixes and are sufficient .

In the same piece ： Prefix and with a method similar to that inside the hash .

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("ok\n")

inline ll read(){
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {
    if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)) {
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
bool mem1;

const int N=1e5+100;
const int inf=1e9+100;
const bool Flag=0;
const int mod=1e9+7;

const int B=405;//number of block
const int S=405;//size of block

int n,m;
int pos[N],a[N],b[N],rk[N];
int st[B],ed[B],bel[N],w,len[B];
int sum[B][N],pre[N][S],val[B][S],pl[B][S];
int f[B][B][S],s[B][S][S];
int lb[B][N];
int u[S],v[S],n1,n2;
void init(){
    
  w=sqrt(n);
  for(int i=1;i<=n;i++) bel[i]=(i+w-1)/w;
  for(int k=1;k<=bel[n];k++){
    
    st[k]=(k-1)*w+1;
    ed[k]=min(n,k*w);
    len[k]=ed[k]-st[k]+1;
    sort(b+st[k],b+ed[k]+1);
    for(int i=st[k];i<=ed[k];i++){
    
      int suf=i==ed[k]?n+1:b[i+1];
      for(int j=b[i];j<suf;j++){
    
	lb[k][j]=i-st[k]+1;
      }
    }
    for(int i=st[k];i<=ed[k];i++) rk[pos[b[i]]]=i-st[k]+1;
    for(int i=1;i<=n;i++) sum[k][i]=sum[k-1][i];
    for(int i=st[k];i<=ed[k];i++){
    
      sum[k][a[i]]++;
      if(i!=st[k]){
    
	for(int j=1;j<=len[k];j++) pre[i][j]=pre[i-1][j];
      }
      pre[i][rk[i]]++;
      pl[k][rk[i]]=i;
      val[k][rk[i]]=a[i];
    }    
  }
  for(int i=1;i<=n;i++){
    
    for(int j=1;j<=len[bel[i]];j++) pre[i][j]+=pre[i][j-1];
  }
  for(int k=1;k<=bel[n];k++){
    
    for(int a=1;a<=len[k];a++){
    
      for(int b=a+1;b<=len[k];b++){
    
	int p=pl[k][b];
	s[k][a][b]=s[k][a][b-1]+(pre[p][b-1]-pre[p][a-1]);
      }
    }
  }
  for(int k=1;k<=bel[n];k++){
    
    for(int i=1;i<=n;i++) sum[k][i]+=sum[k][i-1];
  }
  for(int i=1;i<=bel[n];i++){
    
    for(int j=1;j<i;j++){
    
      for(int k=1;k<=len[i];k++){
    
	f[i][j][k]=sum[j][b[st[i]+k-1]]+f[i][j][k-1];
      }
    }
  }
  return;
}
void work(int l,int r,int bot,int top){
    
  if(l>r||bot>top){
    
    puts("0");
    return;
  }
  int x=bel[l],y=bel[r];
  if(x==y){
    
    ll res(0);
    for(int i=l;i<=r;i++){
    
      if(a[i]>=bot&&a[i]<=top){
    
	res+=(pre[i][rk[i]-1]-(l==st[x]?0:pre[l-1][rk[i]-1]))-(pre[i][lb[x][bot-1]]-(l==st[x]?0:pre[l-1][lb[x][bot-1]]));
      }
    }
    printf("%lld\n",res);
    return;
  }
  ll res(0);
  for(int i=x+1;i<y;i++){
    
    res+=s[i][lb[i][bot-1]+1][lb[i][top]];
  }
  for(int i=l;i<=ed[x];i++){
    
    if(a[i]>=bot&&a[i]<=top){
    
      res+=(pre[i][rk[i]-1]-(l==st[x]?0:pre[l-1][rk[i]-1]))-(pre[i][lb[x][bot-1]]-(l==st[x]?0:pre[l-1][lb[x][bot-1]]));
    }
  }
  for(int i=st[y];i<=r;i++){
    
    if(a[i]>=bot&&a[i]<=top){
    
      res+=pre[i][rk[i]-1]-pre[i][lb[y][bot-1]];
    }
  }
  int pp=st[x],cnt(0);
  for(int i=st[y];i<=ed[y];i++){
    
    while(pp<=ed[x]&&b[pp]<b[i]){
    
      cnt+=(pos[b[pp]]>=l&&b[pp]>=bot&&b[pp]<=top);
      ++pp;
    }
    if(pos[b[i]]<=r&&b[i]>=bot&&b[i]<=top) res+=cnt;
  }
  for(int i=l;i<=ed[x];i++){
    
    if(a[i]>=bot&&a[i]<=top) res+=(sum[y-1][top]-sum[x][top])-(sum[y-1][a[i]]-sum[x][a[i]]);
  }
  for(int i=st[y];i<=r;i++){
    
    if(a[i]>=bot&&a[i]<=top) res+=(sum[y-1][a[i]]-sum[x][a[i]])-(sum[y-1][bot-1]-sum[x][bot-1]);
  }
  for(int k=x+1;k<y;k++){
    
    if(lb[k][bot-1]<lb[k][top]){
    
      res+=(f[k][k-1][lb[k][top]]-f[k][x][lb[k][top]])-(f[k][k-1][lb[k][bot-1]]-f[k][x][lb[k][bot-1]]);
      res-=1ll*(lb[k][top]-lb[k][bot-1])*(sum[k-1][bot-1]-sum[x][bot-1]);
    }
  }
  printf("%lld\n",res);
}

bool mem2;
signed main(){
    
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  debug("mem=%.4lf\n",abs(&mem2-&mem1)/1024./1024);
  n=read();m=read();
  for(int i=1;i<=n;i++){
    
    b[i]=a[i]=read();pos[a[i]]=i;
  }
  init();
  for(int i=1;i<=m;i++){
    
    int l=read(),r=read(),bot=read(),top=read();
    work(l,r,bot,top);
  }
  return 0;
}