P1972 [SDOI2009]HH的项链
P1972 [SDOI2009]HH的项链
经典区间数颜色问题。
离线做法有树状数组和莫队，在线做法有主席树。
莫队做法十分暴力，直接维护每个数当前的 cnt 再在单点更新的时候更新答案即可。
树状数组做法：
对于每一个位置维护一个前缀位置 \(pre\)，那么询问就相当于是询问区间多少个位置的 \(pre\) 在 \(l\) 之前。
我们可以考虑离线下来然后差分，具体来说就是每次维护当前点为右端点，左端点为 1 时的值域树状数组，维护小于等于数 x 的 pre 有多少个，这个信息显然可以差分。
然后主席树做法就是在线维护，每次直接在多树上询问即可。
树状数组代码：
#include
#include
#include
#include
using namespace std;
struct node{
int l,r;
int before;
int ans;
}q[1000005];
int a[1000005],n,m,c[1000005],pre[1000005],used[1000005],p[1000005];
inline int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline int lowbit(int x){return x&(-x);}
inline bool cmp(node o,node p){return o.r 莫队
#include
using namespace std;
#define ri register int
#define MAXN 1001000
#define MAXA 1001000
#define MAXQ 1001000
#include
int a[MAXN],cnt[MAXA],bnum,q,n,belong[MAXA],siz,ans1[MAXQ];
struct node{
int l,r,id;
}lin[MAXQ];
struct _io {
char* s;
_io() : s((char*)mmap(0, 1 << 25, PROT_READ, MAP_PRIVATE, fileno(stdin), 0)) {}
operator int() {
int x = 0,w=0;
while((*s)<'0') w|=(!((*s)^45)),++s;
while((*s)>='0') x=(x<<3)+(x<<1)+((*s++)&15);
return x*(w?-1:1);
}
} it;
#define read() it
template< typename T >inline void write(T x)
{
if(x>9) write(x/10);
putchar(x%10^48);
}
inline bool cmp(node a,node b)
{
return (belong[a.l]^belong[b.l])?belong[a.l]b.r);
}
int main()
{
n=read();
siz=2135;
bnum=ceil((double)n/siz);
for(ri i=1;i<=n;++i)
{
belong[i]=i/siz;
}
for(ri i=1;i<=n;++i) a[i]=read();
q=read();
for(ri i=1;i<=q;++i)
{
lin[i].l=read(),lin[i].r=read();
lin[i].id=i;
}
sort(lin+1,lin+1+q,cmp);
int l=1,r=0,now=0;
for(ri i=1;i<=q;++i)
{
int ql=lin[i].l,qr=lin[i].r;
while(lql) now+=!cnt[a[--l]]++;
while(rqr) now-=!--cnt[a[r--]];
ans1[lin[i].id]=now;
}
for(ri i=1;i<=q;++i)
{
write(ans1[i]);
putchar('\n');
}
}