首页 > 代码库 > Codeforces Round 261 Div.2 D Pashmak and Parmida's problem --树状数组

Codeforces Round 261 Div.2 D Pashmak and Parmida's problem --树状数组

2024-07-18 00:48:49   220人阅读

题意：给出数组A，定义f(l,r,x)为A[]的下标l到r之间，等于x的元素数。i和j符合f(1,i,a[i])>f(j,n,a[j])，求有多少对这样的(i,j).

解法：分别从左到右，由右到左预处理到某个下标为止有多少个数等于该下标，用map维护。

然后树状数组更新每个f(j,n,a[j])，预处理完毕，接下来，从左往右扫过去，每次从树状数组中删去a[i]，因为i != j，i不能用作后面的统计，然后统计getsum(inc[a[i]]-1),

(inc表示从左到右)，即查询比此时的a[i]小的f(j,n,a[j])个数。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <map>#define lll __int64using namespace std;using namespace __gnu_cxx;#define N 1000007#define M 22int c[N],a[N];map<int,int> inc,des;int n;int lowbit(int x){    return x & (-x);}void modify(int x,int val){    while(x <= n)    {        c[x] += val;        x += lowbit(x);    }}int getsum(int x){    int res = 0;    while(x > 0)    {        res += c[x];        x -= lowbit(x);    }    return res;}int main(){    int i;    inc.clear();    des.clear();    memset(c,0,sizeof(c));    scanf("%d",&n);    for(i=1;i<=n;i++)        scanf("%d",&a[i]);    for(i=n;i>=1;i--)    {        des[a[i]]++;        modify(des[a[i]],1);    }    lll ans = 0;    for(i=1;i<=n;i++)    {        inc[a[i]]++;        modify(des[a[i]],-1);        des[a[i]]--;        ans += getsum(inc[a[i]]-1);    }    printf("%I64d\n",ans);    return 0;}
View Code

 


联系
我们