简单分析一下,对于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 ;
}

最新文章

  1. RocketMQ原理解析-Remoting
  2. angular+ionic返回上一页并刷新
  3. &lt;实训|第七天&gt;横扫Linux磁盘分区、软件安装障碍附制作软件仓库
  4. editplus快捷键大全其他editplus快捷键
  5. centos7 设置中文
  6. 锋利的jQuery读书笔记---jQuery中Ajax--load方法
  7. Php 笔记3-----php与 asp的等价关系
  8. Android虚拟机运行问题之小结
  9. rt: Unknown command &#39;PATH=&#39;
  10. ThinkPHP学习 volist标签高级应用之多重嵌套循环、隔行变色(转)
  11. lnmp源码安装以及简单配置
  12. timeout Timeout时间已到.在操作完成之前超时时间已过或服务器未响应
  13. Linq第一讲
  14. visual core 运行 .net core bug处理
  15. 【NOI2014】魔法森林
  16. Python3 字典
  17. Spark Distributed matrix 分布式矩阵
  18. mysql数据库通过二进制 -【恢复数据记录】
  19. oracle11g客户端配置及使用(Windows系统)
  20. Java 底层机制(JVM/堆/栈/方法区/GC/类加载)

热门文章

  1. 核K-均值聚类(Kernel K-means Clustering)
  2. 【模板】ST表 洛谷P1816 忠诚
  3. h5滚动页面固定导航
  4. java路径中&#39;/&#39;的使用
  5. MySQL遇到经典例子--(遇到就写)
  6. PHP学习(字符串操作)
  7. 大数据技术之Kafka
  8. docker--docker基本命令使用及发布镜像
  9. Directx11教程36 纹理映射(6)
  10. 1-1.go开发工具安装