1878: [SDOI2009]HH的项链 - #include <Seter> - using namespace Orz;

1878: [SDOI2009]HH的项链

Seter posted @ 2011年12月17日 20:56 in BZOJ with tags SDOI SegTree , 1139 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=1878

RunID User Problem Result Memory Time Language Code Length Submit Time
178975 Seter 1878 Accepted 11496 kb 400 ms C/Edit 907 B 2011-12-17 20:36:09

其实很想写在线划分树虐这题……但是考虑到我有可能会晕或者会吐,最后还是写了萎缩的离线算法!

第一次交居然忘了删掉调试输出……我太2了,看着输出中一堆乱七八糟的东西居然高兴地交了上去

原来printf这么慢……我一开始写出来rank2,膜拜了tim的代码后发现他加了个输出优化,然后我也加了,速度几乎快了一半……

将数字从左到右插入,每插入一个数字就处理右端点是这个点的所有询问。即插入一个数后要维护这个点之前的所有点,到这个点的区间内不同数字个数。

设当前点为b,考虑这个点的数字前一次出现的点i:

1.如果左端点a在点1..i中,那么a..b中不同数字的个数和a..b-1是一样的(i和b相同,可以忽略b)。

2.如果左端点a在点i+1..b-1中,那么a..b中不同数字个数就是a..b-1中不同数字个数+1(即b所对应的数字)。

3.b对应的数字还没出现过,那么不管左端点在哪里都+1,参照2

4.左端点就是b,那么答案显然是1

于是我们其实每次做的事情就是给i+1..b这个区间+1。每个询问就是询问某个位置上的数是多少。

显然可以线段树/树状数组……树状数组的区间+1就是(1..b)+1后(1..i)-1。

 

#include <stdio.h>
int a[50000],n,i=-1,m,k[50001],q[1000001];
char str[3000000],*p=str,out[1000000],*o=out;
struct query{struct query *next;int l,a}*map[50001],st[200000];
inline void I(x,y){for(;x;x-=x&-x)k[x]+=y;}
inline Q(x){int ans=0;for(;x<=i;x+=x&-x)ans+=k[x];return ans;}
inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}main(){
	int l,r;char buf[10];fread(p,1,3000000,stdin);
	for(n=getint();++i!=n;a[i]=getint());
	for(i=m=getint();i--;(map[r]=st+i)->l=l){l=getint();st[i].next=map[r=getint()];}
	for(i=0;i!=n;)for(I(q[a[i]],-1),I(q[a[i]]=++i,1);map[i];map[i]=map[i]->next)map[i]->a=Q(map[i]->l);
	for(;m--;*o++='\n')if(!st[m].a)*o++=48;
	else{
		for(l=0;st[m].a;st[m].a/=10)buf[l++]=st[m].a%10+48;
		while(l--)*o++=buf[l];
	}*--o=0;
	return puts(out),0;
}
By Seter

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee