洛谷P 1972:[SDOI 2009]HHのネックレス(モス/線分樹)
1269 ワード
タイトル転送ゲート: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):
分析:本題には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