重庆网站建设公司哪家好,做网站导航用什么开元程序,科技型中小企业,互联网平台运营是做什么的题目描述 萧薰儿是古国的公主#xff0c;平时的一大爱好是采花。 今天天气晴朗#xff0c;阳光明媚#xff0c;公主清晨便去了皇宫中新建的花园采花。 花园足够大#xff0c;容纳了n朵花#xff0c;花有c种颜色#xff08;用整数1-c表示#xff09;#xff0c;且花是排…题目描述 萧薰儿是古国的公主平时的一大爱好是采花。 今天天气晴朗阳光明媚公主清晨便去了皇宫中新建的花园采花。 花园足够大容纳了n朵花花有c种颜色用整数1-c表示且花是排成一排的以便于公主采花。公主每次采花后会统计采到的花的颜色数颜色数越多她会越高兴同时她有一癖好她不允许最后自己采到的花中某一颜色的花只有一朵。为此公主每采一朵花要么此前已采到此颜色的花要么有相当正确的直觉告诉她她必能再次采到此颜色的花。 由于时间关系公主只能走过花园连续的一段进行采花便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了m个行程然后一一向你询问公主能采到多少朵花她知道你是编程高手定能快速给出答案最后会选择令公主最高兴的行程为了拿到更多奖金。 说明 n,m,c≤2∗10^6 题解 一句话题意求询问区间内出现次数大于1的数有多少个。 直接处理不现实。可以离线。 询问按照左端点排序。 可以类比HH的项链、 预处理每个点nxt[i]表示i位置相同颜色的下一个位置。 树状数组每个点点的值是c为1的含义是这个点在当前询问区间左端点为L的时候是从L开始的第二个出现的这个数c 开始把所有颜色第二次出现的位置1 那么对于所有的询问左端点为L的询问直接query(r)-query(l-1)即可。 可以理解第三次及以上出现的不算重一次的也不会算。必须r包含第二次出现的才会统计上。 L右移的时候把nxt[L]-1,nxt[nxt[L]]1因为nxt[L]原来是第二个现在会变成第一个。 nxt[nxt[L]]就变成第二个了。 代码 #includebits/stdc.h
using namespace std;
const int N20000005;
int n,m,c;
int has[N],nxt[N];
int a[N];
int f[N];
void add(int x,int d){for(;xn;xx(-x)) f[x]d;
}
int query(int x){int ret0;for(;x;x-x(-x)) retf[x];return ret;
}
struct node{int l,r;int id;bool friend operator (node a,node b){return a.lb.l;}
}q[N];
int ans[N];
int pos[N];
int main()
{scanf(%d%d%d,n,c,m);for(int i1;in;i){scanf(%d,a[i]);has[a[i]];if(pos[a[i]])nxt[pos[a[i]]]i;if(has[a[i]]2) add(i,1);pos[a[i]]i;}int l,r;for(int i1;im;i){scanf(%d%d,q[i].l,q[i].r);q[i].idi;}sort(q1,qm1);int L1;for(int i1;im;i){while(Lq[i].l){if(nxt[L]) add(nxt[L],-1);if(nxt[nxt[L]]) add(nxt[nxt[L]],1);L;}ans[q[i].id]query(q[i].r)-query(q[i].l-1);}for(int i1;im;i){printf(%d\n,ans[i]);}return 0;
} 总结对于离线区间询问的情况——BY LYD 1.cdq分治对于前一半对后一半的影响 2.整体二分对于答案 3.区间排序对于处理答案先后顺序便于区间之间转化的时候降低复杂度经典的有如莫队转载于:https://www.cnblogs.com/Miracevin/p/9676591.html
