考虑以块大小为$32$将序列分块，设$s[i][j]$表示前$i$块和前$j$块矩形相交的对数，$f[i][j]$表示矩形$i$和前$j$块的相交个数。

如果矩形$i$和$j$相交，那么有：

$x_1[j] < x_2[i]$

$x_2[j] > x_1[i]$

$y_1[j] < y_2[i]$

$y_2[j] > y_1[i]$

将这$4$维分开处理，对于每一维按相应参数排序，维护一个集合，支持加入以及求交。这显然可以通过bitset在$O(\frac{n^2}{32})$的时间内完成。

通过bitset求出某个矩形$i$和所有矩形的相交情况后，即可在$O(\frac{n}{32})$的时间内更新$s$和$f$。

然后对$s$和$f$求前缀和即可完成$s$和$f$的预处理。

对于查询，首先整块的部分可以通过$s$查询，然后暴力往右往上扩展，用$f$做到$O(1)$询问。对于块内零散部分，暴力检验即可。

每次查询的复杂度为$O(32^2)$。

因为$n$个bitset存不下，注意到bitset加入元素是$O(1)$的，所以考虑再次分块。每加入$128$个元素后备份一次，即可满足内存限制。

总时间复杂度$O(\frac{n^2}{32}+q\times 32^2)$。

 

#include
     
      #include
      
       using namespace std;const int N=30000,M=938,MAXB=235;int n,m,block,i,j,k,l,r,cnt[65536],s[M][M],ans;int A[N],B[N],C[N],D[N],E[N];unsigned short f[N][M];struct P{int x1,y1,x2,y2;}a[N];inline bool cmpa(int x,int y){return a[x].x1
       
        a[y].x2;}inline bool cmpc(int x,int y){return a[x].y1
        
         a[y].y2;}inline bool cmpe(int x,int y){return a[x].y1>a[y].y1;}inline int popcount(unsigned int x){return cnt[x&65535]+cnt[x>>16];}struct Bitset{  unsigned int v[M];  Bitset(){}  inline void clear(){for(int i=0;i<=m;i++)v[i]=0;}  inline void set(int x){v[x>>5]|=1U<<(x&31);}  inline void copy(const Bitset&p){for(int i=0;i<=m;i++)v[i]=p.v[i];}  inline void operator&=(const Bitset&p){for(int i=0;i<=m;i++)v[i]&=p.v[i];}}bA[MAXB],bB[MAXB],bC[MAXB],bD,now,tmp;inline bool check(const P&a,const P&b){  return b.x1
         
          a.x1&&b.y1
          
           a.y1;}inline int ask(int x,int y){ if(x<0||y<0)return 0; int ret=0,c=x>>5<<5,d=y>>5<<5,i,j; if(x>31&&y>31)ret=s[(x>>5)-1][(y>>5)-1]; for(i=c;i<=x;i++)for(j=d;j<=y;j++)if(check(a[i],a[j]))ret++; if(x>31)for(i=d;i<=y;i++)ret+=f[i][(x>>5)-1]; if(y>31)for(i=c;i<=x;i++)ret+=f[i][(y>>5)-1]; return ret;}inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int main(){ read(n); for(i=0;i
           
            >5; for(i=1;i<65536;i++)cnt[i]=cnt[i>>1]+(i&1); block=(n-1)>>7; for(i=0;i
            
             y.y1)bD.set(D[j++]); now.copy(bD); for(k=0;k<=block;k++){ r=min(k<<7|127,n-1); if(a[A[r]].x1>=y.x2)break; } if(k)tmp.copy(bA[k-1]);else tmp.clear(); if(k<=block){ l=k<<7; while(a[A[l]].x1
             
              y.x1)tmp.set(B[l++]); } now&=tmp; for(k=0;k<=block;k++){ r=min(k<<7|127,n-1); if(a[C[r]].y1>=y.y2)break; } if(k)tmp.copy(bC[k-1]);else tmp.clear(); if(k<=block){ l=k<<7; while(a[C[l]].y1
              
               >5][k]+=f[x][k]; if(k)f[x][k]+=f[x][k-1]; } } for(i=0;i<=m;i++)for(j=0;j<=m;j++){ if(i)s[i][j]+=s[i-1][j]; if(j)s[i][j]+=s[i][j-1]; if(i&&j)s[i][j]-=s[i-1][j-1]; } read(m); while(m--){ read(i),read(j),read(l),read(r); i^=ans,j^=ans,l^=ans,r^=ans; i--,j--,l--,r--; printf("%d\n",ans=ask(j,r)-ask(i-1,r)-ask(j,l-1)+ask(i-1,l-1)); } return 0;}