CF459D Pashmak and Parmida's problem （树状数组）

 

Codeforces Round #261 (Div. 2)

 

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

题解：使用树状数组统计小于某数的元素数量。

我们可以先把f(1,i,a[i])和f(j,n,a[j])写出来，观察一下，例如样例1：

n=7

A　　1　　2　　1　　1　　2　　2　　1

R　　4　　3　　3　　2　　2　　1　　1

L　　1　　1　　2　　3　　2　　3　　4

其中A为给定的数组，Rj为f(j,n,a[j])，Li为f(1,i,a[i])。

对每个Li，我们要统计的其实就是符合（j>i，且Rj<Li）的Rj的个数。就是这个Li右边有多少个比它小的Rj。

这样我们可以用树状数组，把Rj各个数的数量全存到树状数组里，例如这个样例就是4有1个，3有2个，2有2个，1有2个。然后从左到右遍历Li，每次从树状数组里删掉Rj，并且求sum(Li-1)，也就是树状数组中1~Li-1的和，也就是比Li小的元素个数。

例如这个样例，到L3时，树状数组里记了2个1和2个2（1个4和2个3在之前被删掉了），L3=2，则sum(L3-1)=sum(2)=1的数量+2的数量=3。ans+=3。

核心代码（b和d是map，用来统计元素个数，超碉）：

ll farm(){
    int i;
    ll re=0;
    b.clear();d.clear();
    REPD(i,n){
        b[a[i]]++;
        update(b[a[i]],1);
    }
    REP(i,n){
        d[a[i]]++;
        update(b[a[i]],-1);
        b[a[i]]--;
        re+=sum(d[a[i]]-1);
        //cout<<i<<' '<<d[a[i]]-1<<' '<<sum(d[a[i]]-1)<<' '<<re<<endl;
    }
    return re;
}

 

全代码：

//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usll unsigned ll
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define REPD(i,n) for(i=(n)-1;i>=0;i--)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) prllf("%d\n",x);
#define RE  freopen("D.in","r",stdin)
#define WE  freopen("1biao.out","w",stdout)
#define mp make_pair
const int maxn=1123456;
ll c[maxn];
int a[maxn];
int n;

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

void update(int x,int y){
    if(!x)return;
    while(x<=n){
        c[x]+=y;
        x+=lowbit(x);
    }
}

ll sum(int x){
    ll re=0;
    while(x>0){
        re+=c[x];
        x-=lowbit(x);
    }
    return re;
}

map<int,int> b,d;

ll farm(){
    int i;
    ll re=0;
    b.clear();d.clear();
    REPD(i,n){
        b[a[i]]++;
        update(b[a[i]],1);
    }
    REP(i,n){
        d[a[i]]++;
        update(b[a[i]],-1);
        b[a[i]]--;
        re+=sum(d[a[i]]-1);
        //cout<<i<<' '<<d[a[i]]-1<<' '<<sum(d[a[i]]-1)<<' '<<re<<endl;
    }
    return re;
}

int main(){
    int i;
    scanf("%d",&n);
    REP(i,n) scanf("%d",&a[i]);
    printf("%I64d\n",farm());
    return 0;
}