洛谷P 1972:[SDOI 2009]HHのネックレス(モス/線分樹)


タイトル転送ゲート:https://www.luogu.org/problem/show?pid=1972
分析:本題にはO(n*log(n))の線分木もあれば、O(n*sqrt(n))の莫隊もある.線分ツリーの方法:
http://blog.csdn.net/kscla/article/details/70227098
以下に莫隊のコードを貼ります(実は暴力で、毎回Rポインタを右に移動させてからLポインタを移動することに注意して、さもなくばL>Rの情況が現れる可能性があって、それからWA):
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const int maxn=50010;
const int maxm=200100;
const int maxv=1000010;

struct data
{
	int L,R,t;
} ask[maxm];

int a[maxn];
int num[maxv];
int temp[maxm];

int n,m;
int sn;

int Get(int x)
{
	if (!x) return 0;
	return (x-1)/sn+1;
}

bool Comp(data x,data y)
{
	int dx=Get(x.L);
	int dy=Get(y.L);
	return ( dxask[i].L)
		{
			nL--;
			if (!num[ a[nL] ]) ans++;
			num[ a[nL] ]++;
		}
		
		while (nL