Tufurama CodeForces - 961E (思维+主席树)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Tufurama CodeForces - 961E (思维+主席树)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1492字，纯文字阅读大概需要3分钟。
内容图文
题意：一个电视剧有n季，每季有a[i]集，当x!=y,存在一对第x季第y集与第y季第x集冲突，(前题是a[x]>=y,a[y]>=x) 。问这个电视剧一共有多少对冲突。
分析：首先如果某季的集数大于n，我们直接让他等于n。
再把这题抽象一下，大概就是让我们求出 ，对于每个下标i,有多少个下标j满足i<j<=a[i],且a[j]>=i,
也就是对每个a[i]>i的下标i，求出序列a的[i+1,n]区间内有多少个数的大小属于[i,n]区间内， 这样看来就是主席树模板题。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5+7;
const int mx = 50;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+1;
//题目相当于 给定序列a ,对于每个i
//求出满足i<j<=a[i] 且a[j]>=i的j的数目 累加起来就是答案
ll tree[maxn*mx];
int lc[maxn*mx],rc[maxn*mx],cnt=0,root[maxn];
int n;
int a[maxn];
void updata(int &rt,int last,int l,int r,int pos)
{
rt=++cnt;
tree[rt]=tree[last]+1;
lc[rt]=lc[last],rc[rt]=rc[last];
if(l==r) return ;
int mid=(l+r)>>1;
if(pos<=mid) updata(lc[rt],lc[last],l,mid,pos);
else updata(rc[rt],rc[last],mid+1,r,pos);
}
ll query(int rt1,int rt2,int l,int r,int vl)//大于等于vl的所有值
{
if(l>=vl) return tree[rt2]-tree[rt1];
int mid=(l+r)>>1;
if(vl<=mid) return query(lc[rt1],lc[rt2],l,mid,vl)+tree[rc[rt2]]-tree[rc[rt1]];
else if(vl>mid) return query(rc[rt1],rc[rt2],mid+1,r,vl);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
a[i]=min(a[i],n);
updata(root[i],root[i-1],1,INF,a[i]);
}
ll ans=0;
for(int i=1;i<=n;i++)
{
if(a[i]>i)//wa点
ans+=query(root[i],root[a[i]],1,INF,i);
}
cout<<ans<<endl;
return 0;
}
内容总结
以上是互联网集市为您收集整理的Tufurama CodeForces - 961E (思维+主席树)全部内容，希望文章能够帮你解决Tufurama CodeForces - 961E (思维+主席树)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。