【树状数组】CF961E Tufurama
挺巧妙的数据结构题(不过据说这是一种套路?
E. Tufurama
TV series have n seasons (numbered 1 through n), the i-th season has ai episodes (numbered 1 through ai). Polycarp thinks that if for some pair of integers x and y (x < y) exist both season x episode y and season y episode x then one of these search queries will include the wrong results. Help Polycarp to calculate the number of such pairs!
The first line contains one integer n (1 ≤ n ≤ 2·10^5) — the number of seasons.
The second line contains n integers separated by space a1, a2, ..., an (1 ≤ ai ≤ 10^9) — number of episodes in each season.
Print one integer — the number of pairs x and y (x < y) such that there exist both season x episode y and season y episode x.
题目大意
有一部电视剧有n季,每一季有ai集。定义二元组(i,j):存在第i季有第j集。求(i,j)与(j,i)同时合法(i<j)的对数。
真实题意就是:求<i,j>对数,使得a[i]≥j,a[j]≥i并且(i<j)
看上去很可做的样子,对吧……
题目分析
基础的暴力
从1..n季,每一季都分别判断对答案的贡献。
例如对于 4 \n ,依次检查(1,2)是否存在(2,1);(1,3)是否存在(3,1)……
首先发现a[i]对于答案的贡献最大也就是到n为止,那么读入时候先取个min(n)。
考虑一下check()是O(n)的,所以总复杂度是O(n²)的。
BIT做法
像很多其他题一样,对于这样的、关于元素大小关系之间的限制的题目,先排个序总是能够解决个一维限制掉去的。
我们使用一个结构体node x,x.i表示季数;x.a表示该季的集数。首先对x.a排序。那么就变成这个样子:
p[].a(j) 3 5 1 2
p[].i(i) 1 2 3 4
|
|
p[].a(j) 1 2 3 4 (取min之后)
p[].i(i) 3 4 1 2
先考虑每次的统计,那么只要ans+=query(a[i])就可以了。意思就是说ans加上1..a[i]季的贡献(其中每一季的贡献要么是0要么是1,但是由于之后会有修改,所以我们用BIT维护)
接着考虑修改,设立一个now指向当前最小合法的p[]。这个now用来更新那些已经 过气 没有贡献的答案。
这里「没有贡献的答案」指的是p[now].a<i的情况。说人话就是p[now]的电视剧集数太小了,已经不会再有贡献了,因此now++,判断下一个p[]是否可能会对答案有贡献。个人感觉有那么一点相似 单调队列 和 wqs二分 的情况(但是我不是非常清楚)?
为了去除这些没有贡献的季数的影响,我们只需将p[now].i位置在树状数组上-1即可。意思是说这个季数在之后的统计上都不会有贡献了。
#include<bits/stdc++.h>
using namespace std;
long long ans;
int n,now,a[];
struct node
{
int a,i;
bool operator < (node &xx) const
{
return a < xx.a;
}
}p[];
int f[];
int read()
{
char ch = getchar();int num = ;
for (; !isdigit(ch); ch = getchar());
for (; isdigit(ch); ch = getchar())
num = (num<<)+(num<<)+ch-;
return num;
}
int lowbit(int x){return x&-x;}
void add(int x, int c){for (; x<=n+; x+=lowbit(x))f[x]+=c;}
int query(int x)
{
int ret = ;
for (; x; x-=lowbit(x))
ret += f[x];
return ret;
}
int main()
{
n = read();now = ;
for (int i=; i<=n; i++)
a[i] = min(read(), n+), p[i].a = a[i], p[i].i = i, add(i, );
sort(p+, p+n+);
for (int i=; i<=n; i++)
{
while (now<=n && p[now].a < i)add(p[now++].i, -);
ans += query(a[i]);
if (a[i] >= i)ans--;
}
cout << ans / << endl;
return ;
}
另附其他做法
其他人用BIT维护也挺巧妙的(但是我觉得初看时候有点云里雾里啊)
1.Educational Codeforces Round 41 E. Tufurama (961E) BIT做法
2.Codeforces 961E - Tufurama 【树状数组】 BIT做法
3.Codeforces - 961E Tufurama set+BIT
END
最新文章
- ORACLE临时表空间总结
- iOS之NSString类中compare方法的陷阱
- 必须知道的八大种排序算法【java实现】(一) 冒泡排序、快速排序
- Jersey the RESTful Web Services in Java
- Hql查询结果动态组装 List(map),List(bean),List(list),List(set)等格式(转)
- SAM4E单片机之旅——14、LCD之SMC的配置
- 正则的小效果:------->; 过滤敏感词
- Python标准库11 多进程探索 (multiprocessing包)
- 修改tomcat的默认编码
- Windows 驱动开发 - 5
- 使用Spire PDF for .NET将HTML转换成PDF文档
- Spring3.2 HelloWorld
- Beta冲刺 总结
- Connection Reset By Peer 解析
- LeetCode--11_Container_With_Most_Water
- 编辑器-vim
- 【hihocoder 1424】 Asa&#39;s Chess Problem(有源汇上下界网络流)
- await异步的,容易理解一点
- private、public、protected和默认
- C#高低位分解转换备忘
热门文章
- flask --db-Column属性
- Sublime Text插件列表
- zblog去除文章页作者信息
- 报错:&#39;byte&#39; does not name a type
- Paoding-Rose学习
- happy2018暑期集训课后习题001
- leetcode--5 Longest Palindromic Substring
- 忽略mysql库的同步
- Android(java)学习笔记95:Android运行时异常";Binary XML file line # : Error inflating class";
- Softmax回归(Softmax Regression