P4113 [HEOI2012]采花
题面
萧薰儿是古国的公主，平时的一大爱好是采花。
今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。
花园足够大，容纳了 \(n\) 朵花，共有 \(c\) 种颜色，用整数 \(1 \sim c\) 表示。且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴。同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。
由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了 \(m\) 个行程，然后一一向你询问公主能采到的花共有几种不同的颜色。
思路
暴力
暴力时间复杂度为 \(O(nm)\)，可以水50分。
// O(nm)
#include
using namespace std;
const int SIZE = 1e6+5;
int n,c,m;
int flower[SIZE];
int bucket[SIZE];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>c>>m;
for(int i=1;i<=n;i++){
cin>>flower[i];
}
while(m--){
memset(bucket,0,sizeof(bucket));
int l,r,ans=0;
cin>>l>>r;
for(int i=l;i<=r;i++){
bucket[flower[i]]++;
}
for(int i=1;i<=c;i++){
if(bucket[i]>1){
ans++;
}
}
cout< 基础莫队
本题和小B的询问很像。
莫队复杂度为 \(O(m \sqrt{n})\)。
#include
#define int long long
using namespace std;
const int SIZE = 2e6+5;
int times[SIZE];int a[SIZE];int ans[SIZE];
int tans;
int block;
int n,m,k;
int ans1=1,ans2=0;
struct query{
int l,r,id;
bool operator<(const query y) const {
if((l-1)/block==(y.l-1)/block) {
return rl){
ans1--;
add(a[ans1]);
}
while(ans2r){
remove(a[ans2]);
ans2--;
}
ans[querys[i].id]=tans;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
n=read(),m=read(),k=read();
swap(m,k);
block=sqrt(n);
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=m;i++){
querys[i].l=read();
querys[i].r=read();
querys[i].id=i;
}
sort(querys+1,querys+m+1);
for(int i=1;i<=m;i++){
modui(querys[i].l,querys[i].r,i);
}
for(int i=1;i<=m;i++){
cout< 可以水 100 分。
莫队+奇偶化排序
可以优化到133分。
#include
#define int long long
using namespace std;
const int SIZE = 2e6+5;
int times[SIZE];int a[SIZE];int ans[SIZE];
int tans;
int unit=1314;
int n,m,k;
int ans1=1,ans2=0;
struct query{
int l,r,id;
bool operator<(const query &x) const {
if (l / unit != x.l / unit) return l < x.l;
if ((l / unit) & 1)
return r < x.r;
return r > x.r;
}
} querys[SIZE];
void add(int x){
times[x]++;
if(times[x]==2){
++tans;
}
}
void remove(int x){
times[x]--;
if(times[x]==1){
--tans;
}
}
void modui(int l,int r,int i){
while(ans1>l){
ans1--;
add(a[ans1]);
}
while(ans2r){
remove(a[ans2]);
ans2--;
}
ans[querys[i].id]=tans;
}
namespace IO{
const int SIZE=1<<21;
static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
int qr;
char qu[55],c;
bool f;
#define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
#define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
#define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
#define puts(x) IO::Puts(x)
template
inline void read(T&x){
for(f=1,c=getchar();c<48||c>57;c=getchar())f^=c=='-';
for(x=0;c<=57&&c>=48;c=getchar()) x=(x<<1)+(x<<3)+(c&15);
x=f?x:-x;
}
template
inline void write(T x){
if(!x) putchar(48); if(x<0) putchar('-'),x=-x;
while(x) qu[++qr]=x%10^48,x/=10;
while(qr) putchar(qu[qr--]);
}
inline void Puts(const char*s){
for(int i=0;s[i];i++)
putchar(s[i]);
putchar('\n');
}
struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::write;
signed main(){
read(n);read(m);read(k);
swap(m,k);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<=m;i++){
read(querys[i].l);
read(querys[i].r);
//querys[i].r=read();
querys[i].id=i;
}
sort(querys+1,querys+m+1);
for(int i=1;i<=m;i++){
modui(querys[i].l,querys[i].r,i);
}
for(int i=1;i<=m;i++){
write(ans[i]);
putchar('\n');
}
return 0;
}
正解等待中……