检察院内部网站升级建设,wordpress 采集系统,哪个平台开网店不收费,网络营销的新产品战略题解: http://www.lydsy.com/JudgeOnline/problem.php?id1878 题解: 莫队板子题 核心思想是对区间的询问离线之后按照合理的顺序来优化复杂度 一般的做法是先分块,以左端点所在块为第一关键字,右端点位置为第二关键字排序 用两个指针来跑,这样可以证明的是时间复杂度为O(n√n)…题解: http://www.lydsy.com/JudgeOnline/problem.php?id1878 题解: 莫队板子题 核心思想是对区间的询问离线之后按照合理的顺序来优化复杂度 一般的做法是先分块,以左端点所在块为第一关键字,右端点位置为第二关键字排序 用两个指针来跑,这样可以证明的是时间复杂度为O(n√n) #includecstdio
#includealgorithm
#includecstring
#includecmath
#define N 50005
#define M 1000005
#define Q 200005
using namespace std;
int n,m,S,l,r,tl,tr,tot,ans[Q],a[N],cnt[M];
struct node
{int l,r,bl,id;bool operator (const node x)const{return blx.bl || blx.bl rx.r;}
}q[Q];
int main()
{scanf(%d,n);Ssqrt(n);for (int i1;in;i)scanf(%d,ai);scanf(%d,m);for (int i1;im;i){scanf(%d%d,l,r);q[i].idi;q[i].ll;q[i].rr;q[i].bl(l-1)/S1;}sort(q1,q1m);for (int i1;im;i){lq[i].l,rq[i].r;while (tll) if (!--cnt[a[tl]]) tot--;while (tll) if (!cnt[a[--tl]]) tot;while (trr) if (!cnt[a[tr]]) tot;while (trr) if (!--cnt[a[tr--]]) tot--;ans[q[i].id]tot;}for (int i1;im;i)printf(%d\n,ans[i]);return 0;
} 转载于:https://www.cnblogs.com/mrsheep/p/8182026.html
