EC Round 41 (Rated for Div. 2)主席树 E. Tufurama
2024-10-08 03:55:27
简单分析一下,对于x<y,求a[x]>=y 同时a[y]>=x
再简化一下,求1-a[y]区间内大于>=y的个数。。。主席树牛逼
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#define LL long long
using namespace std;
const int maxx = 2e5+;
struct node{
int l,r;
int cnt;
}tree[maxx*];
int a[maxx];
int b[maxx];
int root[maxx];
int cnt;
vector<int>v;
int getval(int x){
return lower_bound(v.begin(),v.end(),x)-v.begin()+;
}
void inserts(int l,int r,int pre,int &now,int pos){
now=++cnt;
tree[now]=tree[pre];
tree[now].cnt++;
if(l==r){
return ;
}
int mid=(l+r)>>;
if (pos<=mid){
inserts(l,mid,tree[pre].l,tree[now].l,pos);
}else {
inserts(mid+,r,tree[pre].r,tree[now].r,pos);
}
}
int query(int L,int R,int l,int r,int w){
if(l==r){
return tree[R].cnt-tree[L].cnt;
}
int mid=(l+r)>>;
if(w<=mid){
return tree[tree[R].r].cnt-tree[tree[L].r].cnt+query(tree[L].l,tree[R].l,l,mid,w);
}else {
return query(tree[L].r,tree[R].r,mid+,r,w);
}
}
int main(){
int n;
while(~scanf("%d",&n)){
for (int i=;i<=n;i++){
scanf("%d",&a[i]);
v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(int i=;i<=n;i++){
b[i]=getval(a[i]);
}
for (int i=;i<=n;i++){
inserts(,n,root[i-],root[i],b[i]);
}
LL ans=;
for (int i=;i<=n;i++){
ans+=query(root[],root[min(a[i],i-)],,n,getval(i));
}
printf("%lld\n",ans);
}
return ;
}
最新文章
- RocketMQ原理解析-Remoting
- angular+ionic返回上一页并刷新
- <;实训|第七天>;横扫Linux磁盘分区、软件安装障碍附制作软件仓库
- editplus快捷键大全其他editplus快捷键
- centos7 设置中文
- 锋利的jQuery读书笔记---jQuery中Ajax--load方法
- Php 笔记3-----php与 asp的等价关系
- Android虚拟机运行问题之小结
- rt: Unknown command &#39;PATH=&#39;
- ThinkPHP学习 volist标签高级应用之多重嵌套循环、隔行变色(转)
- lnmp源码安装以及简单配置
- timeout Timeout时间已到.在操作完成之前超时时间已过或服务器未响应
- Linq第一讲
- visual core 运行 .net core bug处理
- 【NOI2014】魔法森林
- Python3 字典
- Spark Distributed matrix 分布式矩阵
- mysql数据库通过二进制 -【恢复数据记录】
- oracle11g客户端配置及使用(Windows系统)
- Java 底层机制(JVM/堆/栈/方法区/GC/类加载)