[Codeforces Round #496 (Div. 3)] E2 Median on Segments (General Case Edition)

[Educational Codeforces Round 41] E Tufurama

Zarxdy34 posted @ 2018年7月13日 18:04 in Codeforces with tags 主席树 单调性 , 404 阅读

        题目大意:给定序列\(\{a_n\}\),求有多少对\(x < y\)满足\(a[x] \geq y\)且\(a[y] \geq x\)。\(1 \leq n \leq 2 \cdot 10^5 , 1 \leq a_i \leq 10^9\)。

        题解:可将题目转化为在区间\([1,min(i-1,a[i])]\)中找出满足\(a[x] \geq i\)的x的个数,求和,主席树无脑过。

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10,maxv=maxn*32,maxa=1e9;

struct President_Tree
{
	struct Node
	{
		int sl,sr;
		int sum;
	}P[maxv];
	int root[maxn];
	int Pcnt;

	#define mid ((l+r)>>1)

	void Update(int o)
	{
		P[o].sum=P[P[o].sl].sum+P[P[o].sr].sum;
	}

	void Insert(int l,int r,int pn,int &nn,int x)
	{
		nn=++Pcnt;
		P[nn]=P[pn];
		if (l==r)
		{
			++P[nn].sum;
			return;
		}
		if (x<=mid)
			Insert(l  ,mid,P[pn].sl,P[nn].sl,x);
		else
			Insert(mid+1,r,P[pn].sr,P[nn].sr,x);
		Update(nn);
	}

	void Insert(int n,int x)
	{
		Insert(1,maxa,root[n-1],root[n],x);
	}

	long long Query(int l,int r,int o,int a,int b)
	{
		if (a<=l && r<=b) return P[o].sum;
		long long res=0;
		if (a<=mid) res+=Query(l  ,mid,P[o].sl,a,b);
		if (b> mid) res+=Query(mid+1,r,P[o].sr,a,b);
		return res;
	}

	long long Query(int n,int x)
	{
		return Query(1,maxa,root[n],x,maxa);
	}
}T;

int a[maxn];
int n;
long long ans;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		ans+=T.Query(min(a[i],i-1),i);
		T.Insert(i,a[i]);
	}
	printf("%I64d\n",ans);
	return 0;
}

 

        另一种考虑是,先不管\(x<y\)这个条件,即找出所有的\(a[x] \geq y\)且\(a[y] \geq x\),最后减去\(x \leq a[x]\)的数量,最后再除2。

        从1到n枚举x,可以发现满足\(a[y] \geq x\)的y是不断减少的,即只需找出满足\(y \leq a[x]\)的满足条件的y的数量即可。枚举x的过程中不断删去用不到的y即可。

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;

int lowbit(int x) {return x&-x;}

vector <int> v[maxn];
int a[maxn];
int f[maxn];
int n;
long long ans;

void Change(int x,int p)
{
	while (x<=n) f[x]+=p,x+=lowbit(x);
}

int Query(int x)
{
	int res=0;
	while (x) res+=f[x],x-=lowbit(x);
	return res;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++)
	{
		if (a[i]<=n) v[a[i]].push_back(i);
		Change(i,1);
	}
	for (int i=1;i<=n;i++)
	{
		ans+=Query(min(a[i],n));
		for (auto j:v[i]) Change(j,-1);
	}
	for (int i=1;i<=n;i++) if (i<=a[i]) ans--;
	printf("%I64d\n",ans/2);
	return 0;
}
Avatar_small
PSC Result 2022 Comi 说:
2022年8月30日 01:13

Minister of Education, Bangladesh Mr. Nahid Hasan has announced this year PSC Result 2022 will be announced in the last week of December 2022 with the total or full mark sheet of the Primary School Certificate Exam, <a href="https://bdpscresult2018.com/psc-result-dhaka-board/">PSC Result 2022 Comilla Board</a> based on previous years schedule, once the official date is confirmed we will update here with timings.Previously this Prathomik Somaponi Result 2022 was announced on 30th or 31st December, and this year also announced same for the class 5th grade result with merit or toppers list asper regular GPA Marking schedule, and Directorate of Primary Education (DPE) has announced this year is very tough to conduct evaluation process to announce subject wise marks for Grade 5 terminal exams.

Avatar_small
PSC Result 2022 Comi 说:
2022年8月30日 01:14

Minister of Education, Bangladesh Mr. Nahid Hasan has announced this year PSC Result 2022 will be announced in the last week of December 2022 with the total or full mark sheet of the Primary School Certificate Exam, PSC Result 2022 Comilla Board based on previous years schedule, once the official date is confirmed we will update here with timings.Previously this Prathomik Somaponi Result 2022 was announced on 30th or 31st December, and this year also announced same for the class 5th grade result with merit or toppers list asper regular GPA Marking schedule, and Directorate of Primary Education (DPE) has announced this year is very tough to conduct evaluation process to announce subject wise marks for Grade 5 terminal exams.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter