【BZOJ】[SDOI2009]HH的项链
2024-09-26 17:55:44
【算法】主席树||离线+树状数组
【题解】
主席树经典应用:找区间不同的数字个数。
做法:记录每个数上一次出现的位置last[i],对last建权值线段树,对于区间询问last[i]<L的数字个数。
注意权值范围是last[i],也即0~n。
注意x=0时返回,否则可能c<0就完了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
using namespace std;
const int maxn=;
struct tree{int l,r,sum;}t[];
int a[maxn],n,sz,last[maxn],root[maxn],b[],m; int read()
{
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
void insert(int l,int r,int &x,int y,int c){
x=++sz;
t[x]=t[y];t[x].sum++;
if(l==r)return;
int mid=(l+r)>>;
if(c<=mid)insert(l,mid,t[x].l,t[y].l,c);
else insert(mid+,r,t[x].r,t[y].r,c);
}
int ask(int l,int r,int x,int c){
if(x==)return ;
if(r<=c)return t[x].sum;
int mid=(l+r)>>,ans=;
if(c>mid)ans+=ask(mid+,r,t[x].r,c);
ans+=ask(l,mid,t[x].l,c);
return ans;
}
int main(){
n=read();
for(int i=;i<=n;i++){
a[i]=read();
last[i]=b[a[i]];
b[a[i]]=i;
}
for(int i=;i<=n;i++)insert(,n,root[i],root[i-],last[i]);
m=read();
for(int i=;i<=m;i++){
int u=read(),v=read();
printf("%d\n",ask(,n,root[v],u-)-ask(,n,root[u-],u-));
}
return ;
}
另一种做法,考虑对询问离线并按左端点排序,那么一个位置对答案有贡献仅当左端点已经过和它相同数字的上一位置,那么就是求区间和(有贡献的点+1),显然是树状数组。
具体过程:初始同一个数字最前面的位置+1,然后1~n每次nex[i]位置+1,同时回答询问ans=ask(r)-ask(l-1),因为左端点经过了所以区间同一个数最多只存在一个。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=,maxL=;
int a[maxn],c[maxn],n,m,ans[maxn],anss[maxn],nex[maxn],b[maxL]; int read()
{
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
struct cyc{int l,r,id;}d[maxn];
bool cmp(cyc a,cyc b){return a.l<b.l;}
void insert(int x){for(int i=x;i<=n;i+=lowbit(i))c[i]++;}
int ask(int x){int nowans=;for(int i=x;i>=;i-=lowbit(i))nowans+=c[i];return nowans;}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
a[i]=read();
}
for(int i=;i<=maxL;i++)b[i]=n+;
for(int i=n;i>=;i--){
nex[i]=b[a[i]];
b[a[i]]=i;
}
for(int i=;i<=maxL;i++)if(b[i])insert(b[i]);
scanf("%d",&m);
for(int i=;i<=m;i++){
d[i].l=read();d[i].r=read();
d[i].id=i;
}
sort(d+,d+m+,cmp);
int now=;
for(int i=;i<=n&&now<=m;i++){
while(now<=m&&d[now].l==i){ans[now]=ask(d[now].r)-ask(d[now].l-);now++;}
insert(nex[i]);
}
for(int i=;i<=m;i++)anss[d[i].id]=ans[i];
for(int i=;i<=m;i++)printf("%d\n",anss[i]);
return ;
}
常数约为主席树的1/2。
最新文章
- Can&#39;t find any matching row in the user table
- 在framework中打包xib
- Ubuntu安装nodeJS
- HDU 4622 求解区间字符串中的不同子串的个数
- SVN的405错误
- MVC和Web API 过滤器Filter [转]
- FTP文件操作之删除文件
- Python 2.7.3的文件编码问题,print在控制台下面中文乱码问题,以及推荐做法
- java 强弱引用
- PMD教程
- Android Weekly Notes Issue #284
- mysql-高性能索引策略
- Ubuntu18 的超详细常用软件安装
- ElasticSearch 2.X升级到6.X遇到的几个问题
- P1147连续自然数和-(尺取法)
- mysql 数据库设计
- 【调试技巧】 Fiddler高级用法之url映射请求
- SPOJ 694 Distinct Substrings(不相同子串个数)
- CAS 界面根据不同的域名显示不同的界面
- Roadblocks--poj3255(次短路)
热门文章
- LARK BOARD开发板入门学习-第2篇
- 虚拟现实-VR-UE4-编译UE4源码
- skip-grant-tables 修改linux的mysql忘记root密码
- React远程服务
- [问题解决]Python locale error: unsupported locale setting
- ExtJS6.0扩展日期选择控件为也可以选择时间
- 基于Thinkphp5+phpQuery 网络爬虫抓取数据接口,统一输出接口数据api
- 【bzoj2764】[JLOI2011]基因补全 dp+高精度
- 【题解】JSOI2010满汉全席
- 【题解】洛谷P2418 yyy loves OI IV