[CF961E] Tufurama

Description:

有一天Polycarp决定重看他最喜爱的电视剧《Tufurama》。当他搜索“在线全高清免费观看Tufurama第3季第7集”却只得到第7季第3集的结果时，他很惊讶。这让Polycarp感到疑惑——如果有天他决定重看整个系列却无法找到正确的剧集观看，那该怎么办呢？Polycarp现在想统计一下他被迫用不同方案搜索同一剧集的次数。

电视连续剧有\(n\) 季（从\(1\) 到\(n\) 编号），第\(i\) 季有\(a_i\) 集（从\(1\) 到\(a_i\) 编号）。Polycarp认为如果有一对\(x\) 和\(y\) （\(x\<y\) ），使第\(x\) 季第\(y\) 集、第\(y\) 季第\(x\) 集存在，那么其中一个搜索就会包含错误的内容。请帮助Polycarp统计这样的数对的数量吧！

Hint:

主席树SB题,随便搞个前缀和,离散化都不用

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int mxn=2e5+5;

int n,m,tot,cnt,hd[mxn];

inline int read() {

	char c=getchar(); int x=0,f=1;

	while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}

	while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}

	return x*f;

}

inline void chkmax(int &x,int y) {if(x<y) x=y;}

inline void chkmin(int &x,int y) {if(x>y) x=y;}

struct ed {

	int to,nxt;

}t[mxn<<1];

inline void add(int u,int v) {

	t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;

}

int a[mxn],rt[mxn<<6],ls[mxn<<6],rs[mxn<<6],sz[mxn<<6];

ll ans;

void update(int las,int &p,int l,int r,int pos) {

	if(!p) p=++tot; sz[p]=sz[las]+1;

	if(l==r) return ; int mid=(l+r)>>1;

	if(pos<=mid) update(ls[las],ls[p],l,mid,pos),rs[p]=rs[las];

	else update(rs[las],rs[p],mid+1,r,pos),ls[p]=ls[las];

} 

int query(int p,int l,int r,int pos) {

	if(l==r) return sz[p];

	int mid=(l+r)>>1;

	if(pos<=mid) return sz[rs[p]]+query(ls[p],l,mid,pos);

	else return query(rs[p],mid+1,r,pos);

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i) {

		a[i]=read();

		update(rt[i-1],rt[i],1,n,a[i]);

		ans+=query(rt[min(i-1,a[i])],1,n,i);

	}

	printf("%lld",ans);

    return 0;

}

巴特西

[CF961E] Tufurama

Description:

Hint:

最新文章

热门文章