统计题

给定两个长度分别为 n 和 m 的序列 A 和 B ,有 q 次询问。

每次询问给定四个数 $a,b,c,d$ ，请统计有多少对 $(i,j)$ ，满足 $a≤i≤b,c≤j≤d$ ，且 $A_i+B_j=20220605$。

第一行一个整数 T, 表示数据组数。对于每组数据：

第一行三个整数 n , m 和 q ，分别表示序列 A 的长度，序列 B 的长度和询问的次数

第二行有 n 个整数 $A_1,A_2,A_3,…,A_n$，表示序列 A 的元素。

第三行有 m 个整数 $B_1,B_2,B_3,…,B_m$，表示序列 B 的元素。

由于输入输出文件大小限制，请使用gen()函数生成查询的参数 $a,b,c,d$ 。

int n,m,q,a[50005],b[50005],c[50005],d[50005];
inline unsigned long long xorshift128(){
static unsigned __int128 SX=335634763,SY=873658265,SZ=192849106,SW=746126501;
unsigned __int128 t=SX^(SX<<11);
SX=SY;
SY=SZ;
SZ=SW;
return SW=SW^(SW>>19)^t^(t>>8);
}
inline unsigned long long myrand(){return (xorshift128()<<32)^xorshift128();}
int f(int n){
  return myrand()%(myrand()%n+1)+1;
}
void gen(){
  for(int i=1;i<=q;i++){
    a[i]=f(n),b[i]=n+1-f(n);
    c[i]=f(m),d[i]=m+1-f(m);
    if(a[i]>b[i])swap(a[i],b[i]);
    if(c[i]>d[i])swap(c[i],d[i]);
  }
}

每组询问保证 $1≤a≤b≤n$ 且 $1≤c≤d≤m$。

数据保证 $T≤3,1≤n,m≤100000,1≤q≤50000,1≤A_i,B_j≤10^9$

对于每组数据中的每次询问，输出一个整数，表示询问的结果。

1
10 9 10
21728744 4241503 24040041 28315063 9774131 24040041 24040041 24040041 24040041 9774131
7183681 16354692 5028752 10446474 15979102 19442418 22097733 21292928 15979102

1
1
0
2
1
0
3
2
0
2

杭州电子科技大学第二十二届程序设计竞赛