首页 技术 正文
技术 2022年11月23日
0 收藏 617 点赞 3,352 浏览 1845 个字

【BZOJ5016】[Snoi2017]一个简单的询问

Description

给你一个长度为N的序列ai,1≤i≤N和q组询问,每组询问读入l1,r1,l2,r2,需输出【BZOJ5016】[Snoi2017]一个简单的询问 莫队get(l,r,x)表示计算区间[l,r]中,数字x出现了多少次。

Input

第一行,一个数字N,表示序列长度。第二行,N个数字,表示a1~aN第三行,一个数字Q,表示询问个数。第4~Q+3行,每行四个数字l1,r1,l2,r2,表示询问。N,Q≤50000N1≤ai≤N1≤l1≤r1≤N1≤l2≤r2≤N注意:答案有可能超过int的最大值

Output

对于每组询问,输出一行一个数字,表示答案

Sample Input

5
1 1 1 1 1
2
1 2 3 4
1 1 4 4

Sample Output

4
1

题解:先将询问的l–,然后我们开始推式子喽!为了方便起见,下面用s(i)表示get(1,i,x)。那么:

$ans=\sum\limits_{x}(s(r1)-s(l1))*(s(r2)-s(l2)))\\=\sum\limits_{x}s(r1)*s(r2)+s(l1)*s(l2)-s(l1)*s(r2)-s(r1)*s(l2)\\*ab={(a+b)^2-a^2-b^2\over 2}*\\=\sum\limits_{x}{(s(r1)^2+s(r2)^2-(s(r2)-s(r1)))^2+s(l1)^2+s(l2)^2-(s(l2)-s(l1))^2+(s(r2)-s(l1))^2-s(r2)^2-s(l1)^2+(s(r1)-s(l2))^2-s(r1)^2-s(l2)^2\over 2}\\=\sum\limits_{x}{(s(r1)-s(l2))^2+(s(r2)-s(l1))^2-(s(l2)-s(l1))^2-(s(r2)-s(r1))^2\over 2}$

然后用莫队处理区间中每个数出现次数的平方即可!

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=50010;
struct node
{
int a,b,org,k;
node() {}
node(int x,int y,int c,int d){a=min(x,y)+1,b=max(x,y),org=c,k=d;}
}q[maxn<<2];
int s[maxn],v[maxn];
int n,m,B;
ll sum,ans[maxn];
inline int rd()
{
int ret=0,f=1;char gc=getchar();
while(gc<'0'||gc>'9'){if(gc=='-')f=-f;gc=getchar();}
while(gc>='0'&&gc<='9')ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
bool cmp(node a,node b)
{
return (a.a/B==b.a/B)?(a.b<b.b):(a.a/B<b.a/B);
}
int main()
{
n=rd(),B=int(sqrt(double(n)));
int i,a,b,c,d,l,r;
for(i=1;i<=n;i++)v[i]=rd();
m=rd();
for(i=1;i<=m;i++)a=rd()-1,b=rd(),c=rd()-1,d=rd(),
q[i]=node(a,c,i,-1),q[i+m]=node(b,d,i,-1),q[i+2*m]=node(a,d,i,1),q[i+3*m]=node(b,c,i,1);
sort(q+1,q+4*m+1,cmp);
for(l=1,r=0,i=1;i<=4*m;i++)
{
while(l>q[i].a)l--,s[v[l]]++,sum+=2*s[v[l]]-1;
while(l<q[i].a)sum-=2*s[v[l]]-1,s[v[l]]--,l++;
while(r<q[i].b)r++,s[v[r]]++,sum+=2*s[v[r]]-1;
while(r>q[i].b)sum-=2*s[v[r]]-1,s[v[r]]--,r--;
ans[q[i].org]+=q[i].k*sum;
}
for(i=1;i<=m;i++)printf("%lld\n",ans[i]>>1);
return 0;
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,254
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,692
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,531
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,302
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,942
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,102