网站由哪些部分组成部分组成,酷炫的动漫主题wordpress,重庆有哪些科技骗子公司,江苏省工程建设标准定额网站数据结构题
题目#xff1a;
问在区间[l,r]和[l1,r1]内x的出现次数的乘积是多少#xff1f;
题解#xff1a;
莫队算法的模板题 关于莫队算法你可以参考这个 我这里简单的说说我对莫队的理解#xff1a; 莫队是一个优雅的暴力#xff0c;就是将原本复杂度不能过的程序…数据结构题
题目
问在区间[l,r]和[l1,r1]内x的出现次数的乘积是多少
题解
莫队算法的模板题 关于莫队算法你可以参考这个 我这里简单的说说我对莫队的理解 莫队是一个优雅的暴力就是将原本复杂度不能过的程序进行优化莫队是通过分块来实现 如果暴力做这个题查询区间[l,r]内x的数量我们可能就从头开始搜查按照题目给的数据来搜查但其实我们可以这样优化,比如题目给的查询区间[3,4],[2,4],[1,5],我们可以先查询[1,5],然后顺势查询[2,4],最后[3,4]而非从头开始这样就省了不少时间。那如何实现这个我们可以对整体进行分块然后按照所分的快进行排序尽可能实现查询区间时省时省力最后再输出答案 至于为什么要分块排序呢可以看看莫队算法的讲解 很显然这是一个离线算法且适合查询量很大的情况 代码如下
代码
#includebits/stdc.h
#define forn(i,a,b) for(ll ia;ib;i)
#define INF 0x3f3f3f3f
using namespace std;#define ll long long
const ll N 100*100010;
const ll mod 20180623;
ll n,m;
ll a[N],ans[N*2],num[N],pos[N];
struct node{ll L,R,x,id;
}t[N*2];bool cmp(node a,node b){if(pos[a.L]pos[b.L])return a.Rb.R;else return pos[a.L]pos[b.L];
}ll L1,R0;
void solve(node p){while(p.LL){num[a[L]]--;L;}while(p.RR){R;num[a[R]];}while(p.LL){L--;num[a[L]];}while(p.RR){num[a[R]]--;R--;}
}int main(){scanf(%lld %lld,n,m);memset(num,0,sizeof(num));ll blocksqrt(n);for(ll i1;in;i){scanf(%lld,ai);pos[i]i/block;}for(ll i1;im;i){ll l1,r1,l2,r2,x;scanf(%lld%lld%lld%lld%lld,l1,r1,l2,r2,x);if(l1r1)swap(l1,r1);if(l2r2)swap(l2,r2);t[i].Ll1;t[i].Rr1;t[i].idi;t[i].xx;t[im].Ll2;t[im].Rr2;t[im].idim;t[im].xx;}sort(t1,t12*m,cmp);memset(num,0,sizeof(num));for(ll i1;i2*m;i){solve(t[i]);ans[t[i].id]num[t[i].x];}for(ll i1;im;i)printf(%lld\n%lld\n%lld\n,ans[i]%mod,ans[im]%mod,(ans[i]%mod*ans[im])%mod);return 0;
}
