目录
Description
给你一个长度为 N 的序列 ai,1≤i≤N,和 q 组询问,每组询问读入 l1,r1,l2,r2,需输出
x=0∑∞get(l1,r1,x)×get(l2,r2,x)
get(l,r,x) 表示计算区间 [l,r] 中,数字 x 出现了多少次。
State
\(n,m<=50000\)
\(1<=a[i]<=n\)
Input
5
1 1 1 1 1
2
1 2 3 4
1 1 4 4
Output
4
1
Solution
题目 \(r_1,l_2\) 的大小并不明确,需要另一种新颖的容斥方法
另 \([l,r]\) 为区间内 \(x\) 的个数,\(x\) 任意
之后 \([l1,r1]*[l2,r2]\) 可以转化为
\[[1,r1]*[1,r2]-[1,r1]*[1,l2-1]-[1,r2]*[1,l1-1]+[1,l1-1]*[1,l2-1] \]每一个区间的左端点都为 \(1\),所以可以将一个区间分为 \(4\) 个不同的区间,而他们的左端点都为 \(1\);
也就是说对于每一个端点 \(l,r\) 对于 \(1\) 来说,都是右端点
\(hint:\) 区间大小是题目所给的 \(4\) 倍
Code
const int N = 5e4 * 4 + 5;
int n, m;
int a[N];
struct Query
{
int l, r;
int bel;
int id, tag;
bool operator<(Query o){
return bel == o.bel ? r < o.r: l < o.l;
}
Query(int l = 0, int r = 0, int id = 0, int tag = 0, int bel = 0) : l(l), r(r), bel(bel), id(id), tag(tag){}
}q[N];
int block, pre[N], suf[N];
int tot = 0;
ll ans[N], now;
void add(int pos, int *on, int *nxt)
{
int x = a[pos];
now += nxt[x];
on[x] ++;
}
void del(int pos, int *on, int *nxt)
{
int x = a[pos];
now -= nxt[x];
on[x] --;
}
void mo()
{
block = 3 * sqrt(n);
for(int i = 1; i <= tot; i ++){
if(q[i].l > q[i].r) swap(q[i].l, q[i].r);
q[i].bel = q[i].l / block + 1;
}
sort(q + 1, q + 1 + tot);
}
signed main()
{
while(~ sd(n)){
rep(i, 1, n) sd(a[i]);
sd(m);
rep(i, 1, m){
int x, y, nx, ny;
sdd(x, y); sdd(nx, ny);
q[++ tot] = Query(y, ny, i, 1);
q[++ tot] = Query(x - 1, ny, i, -1);
q[++ tot] = Query(nx - 1, y, i, -1);
q[++ tot] = Query(x - 1, nx - 1, i, 1);
}
mo();
int l = 0, r = 0;
now = 0;
for(int i = 1; i <= tot; i ++){
while(l < q[i].l) add(++ l, pre, suf);
while(l > q[i].l) del(l --, pre, suf);
while(r < q[i].r) add(++ r, suf, pre);
while(r > q[i].r) del(r --, suf, pre);
ans[q[i].id] += now * q[i].tag;
}
rep(i, 1, m) pll(ans[i]);
}
return 0;
}