莫队

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5+10,M = 5e5+10,S = 5e5+10;

int n,m,len;
int w[N],ans[M],cnt[S];

struct Query
{
	int id,l,r;
}q[M];

inline int read()
{
	int x = 0;int f = -1;char c = getchar();
	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}
	while(isdigit(c)){x = (x<<1) + (x<<3) + (c^48);c = getchar();}
	x*=f;
	return x;
}

inline int get(int x)
{
	return x/len;
}

inline bool cmp(const Query& a,const Query& b)
{
	int i = get(a.l),j = get(b.l);
	if(i!=j) return i<j;
	return a.r<b.r; 
}

inline void add(int x,int& res)
{
	if(!cnt[x]) res++;
	cnt[x]++;
}

inline void del(int x,int& res)
{
	cnt[x]--;
	if(!cnt[x]) res--;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	//n = read();
	cin >> n;
	for(int i=1;i<=n;i++) //w[i] = read();
		cin >> w[i];
	//m = read();
	cin >> m;
	len = sqrt((double)n*n/m);
	for(int i=0;i<m;i++)
	{
		int l,r;
		//l = read();r = read();
		cin >> l >> r;
		q[i] = {i,l,r};
	}
	sort(q,q+m,cmp);
	for(int k=0,i=0,j=1,res=0;k<m;k++)
	{
		int id = q[k].id,l = q[k].l,r = q[k].r;
		while(i<r) add(w[++i],res);
		while(i>r) del(w[i--],res);
		while(j<l) del(w[j++],res);
		while(j>l) add(w[--j],res);
		ans[id] = res;
	}
	for(int i=0;i<m;i++) printf("%d\n",ans[i]);
	return 0;
}

田所先生的程序

~众所周知，一般而言，随着经济社会的发展...~

（以上省略114514字）...今天，小编就来给大家带来 田所先生的程序 的...

首先看题，并不复杂，给定一串数列，求区间内不同数字的组数。

如果​~抛开事实不谈~​，这道题似乎可以通过在区间内放集合求长度的方式通过。但显然，这道题会TLE。所以我们需要考虑复杂度更低的方式：

树状数组！

首先来说说具体原理。我们用tree[i]来《树状数组地存储》第i个程序前面的程序数（即前缀和为贝壳种数），用vis[j]来存储j号程序最后一次出现的地方。对所有的询问，以右端点从小到大进行排序，并离线处理。

用pow存储上一个左端点所在的位置，排序后，可证明上一个左端点到现在的右端点区间内，一定存在现在的左端点。

我们的核心代码即为：

int pow=1;
for(int i=1;i<=m;i++){
    for(int j=pow;j<=qu[i].r;j++){
        if(vis[bk[j]])up(bk[j],-1);
        up(bk[j],1);
        vis[bk[j]]=j;
    }
    ans[qu[i].id]=out(qu[i].l-1,qu[i].r);
    pow=qu[i].l+1;
}

那么，完整代码即为：

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int LXB=1e6+10;

int n,m,l,p,k,r;
int bk[LXB],ans[LXB],vis[LXB],tree[LXB];

struct qus
{
    int l,r,id;
}qu[LXB];

void up(int t,int x){
    for(int i=t;i<=n;i+=i&-i)tree[i]+=x;
}

int out(int l,int r){
    int ans=0;
    for(int i=l;i>=1;i-=i&-i)ans-=tree[i];
    for(int i=r;i>=1;i-=i&-i)ans+=tree[i];
    return ans;
}

bool cmp(qus l,qus r){return l.r<r.r;}

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>bk[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>qu[i].l>>qu[i].r;
        qu[i].id=i;
    }
   sort(qu+1,qu+1+m,cmp);
   int pow=1;
   for(int i=1;i<=m;i++){
       for(int j=pow;j<=qu[i].r;j++){
           if(vis[bk[j]])up(bk[j],-1);
           up(bk[j],1);
           vis[bk[j]]=j;
       }
       ans[qu[i].id]=out(qu[i].l-1,qu[i].r);
       pow=qu[i].r+1;
   }
   for(int i=1;i<=m;i++){
       printf("%d\n",ans[i]);
   }
   return 0;//为，美，0
}

不愧是你居然还把我作为一个常变量放在上面

你甚至愿意删掉和shit一样的一长串的define也不愿意把我(const int LXB)移除