题目链接:Codeforces 459D Pashmak and Parmida's problem
题目大意:给定一个序列,定义f(l,r,x)为l≤k≤r并且ak=x的k的个数,求1≤i<j≤n的情况下,f(1,i,ai)<f(j,n,aj)的个数。
解题思路:预处理出f(1,i,ai),f(j,n,aj)值,然后用树状数组维护个数。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
struct state {
int val, pos;
}sta[maxn];
bool cmp (const state& a, const state& b) {
if (a.val != b.val)
return a.val < b.val;
return a.pos < b.pos;
}
int n, c[maxn], f[maxn];
ll v[maxn];
void add (int x, int val) {
while (x <= n) {
v[x] += val;
x += (x & (-x));
}
}
ll sum(int x) {
ll ans = 0;
while (x > 0) {
ans += v[x];
x -= (x &(-x));
}
return ans;
}
ll solve () {
ll ret = 0;
memset(v, 0, sizeof(v));
for (int i = n-1; i >= 0; i--) {
ret += sum(c[i]-1);
add(f[i], 1);
}
return ret;
}
int main () {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &sta[i].val);
sta[i].pos = i;
}
sort(sta, sta+n, cmp);
int pre = -1, cnt = 0;
for (int i = 0; i < n; i++) {
if (pre != sta[i].val) {
pre = sta[i].val;
cnt = 1;
} else
cnt++;
c[sta[i].pos] = cnt;
}
pre = -1, cnt = 0;
for (int i = n; i >= 0; i--) {
if (pre != sta[i].val) {
pre = sta[i].val;
cnt = 1;
} else
cnt++;
f[sta[i].pos] = cnt;
}
printf("%lld\n", solve());
return 0;
}
分享到:
相关推荐
Codeforces 1925D Good Trip 题解
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces部门2,A # And a2oj Ladder 4 some problems Ladder URL:http://a2oj.com/Ladder.jsp?ID=4难度等级:2问题提示: 1- 4A....... http://codeforc
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces-Problem-Set
codeforces每日一练。 题意: 有n张卡片,卡片上的数字就是分数,比如说甲乙两人抽卡,三局两胜,一局得分高的胜,求在甲赢了两局的情况下乙赢了第三局且总分比甲高的概率。 思路: 数据1e3,很明显的On^2算法,所以...
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Educational Codeforces Round 157D. XOR Construction
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
回头重新看了一下题意,这不就是求最长链的树形dp裸题吗? 代码如下: #include #define ll long long #define inf 0x3f3f3f3f #define mod 1000000007 #define PI acos(-1) #define fi first #define se second #...
【并查集】Codeforces 566D Restructuring Company题面在这里对于本题,只需要再维护一个并查集表示i所在联通块的最右位置因为相邻
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 149 D-Coloring Brackets,动态规划求解
Codeforces 185A - Plant 全测试点49个
给出 nnn 个点,n−1n-1n−1 条边,最多询问 n2\frac{n}{2}2n 次,每次询问 u,vu,vu,v,会给出 uvuvuv的最近公共祖先,求树的根。 这个道题单独来看是不难,变成交互题就难了,对于交互题不理解的可以参考这篇博客...
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes