无锡市锡山建设局网站,深圳福田专业网站建设,外贸最热门的十大产品,排行榜哪个网站最好P4396 [AHOI2013]作业
题目描述
详见#xff1a;P4396 [AHOI2013]作业
solution
莫队树状数组的裸题#xff08;莫队分块#xff0c;CDQ分治都可以#xff0c;莫队线段树大概需要卡常#xff09;。
时间复杂度
Code
#includebits/stdc.h
using namespac…P4396 [AHOI2013]作业
题目描述
详见P4396 [AHOI2013]作业
solution
莫队树状数组的裸题莫队分块CDQ分治都可以莫队线段树大概需要卡常。
时间复杂度
Code
#includebits/stdc.h
using namespace std;
const int MAXN2e550;inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}int n,m,Size,Ans1[MAXN],Ans2[MAXN],a[MAXN],cnt[MAXN];
struct pnode{int l,r,a,b,id,x; } p[MAXN];
struct Tree_Array
{int tree[MAXN1];int lowbit(int x){ return x(-x); }void change(int x,int y) { for (;xn;xlowbit(x)) tree[x]y; }int query(int x){ int ans0; for (;x;x-lowbit(x)) anstree[x]; return ans; }
} tree1,tree2;
int compare(pnode x,pnode y){ return (x.xy.x)||(x.xy.xx.ry.r); }
int main()
{nread(),mread(),Sizetrunc(sqrt(n));for (int i1;in;i) a[i]read();for (int i1;im;i){p[i].lread(),p[i].rread(),p[i].aread(),p[i].bread();p[i].idi,p[i].x(p[i].l-1)/Size1;}sort(p1,pm1,compare);int L1,R0;for (int i1;im;i){while (Lp[i].l) cnt[a[L]]--,tree1.change(a[L],-1),tree2.change(a[L],cnt[a[L]]0?-1:0),L;while (Lp[i].l) L--,cnt[a[L]],tree1.change(a[L], 1),tree2.change(a[L],cnt[a[L]]1? 1:0);while (Rp[i].r) R,cnt[a[R]],tree1.change(a[R], 1),tree2.change(a[R],cnt[a[R]]1? 1:0);while (Rp[i].r) cnt[a[R]]--,tree1.change(a[R],-1),tree2.change(a[R],cnt[a[R]]0?-1:0),R--;Ans1[p[i].id]tree1.query(p[i].b)-tree1.query(p[i].a-1);Ans2[p[i].id]tree2.query(p[i].b)-tree2.query(p[i].a-1);}for (int i1;im;i) printf(%d %d\n,Ans1[i],Ans2[i]);return 0;
}
