codeforces 459 D. Pashmak and Parmida's problem（思维+线段树）

题目链接：http://codeforces.com/contest/459/problem/D

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

题解：先预处理一下设map be[a[i]]表示f(1,i,a[i])的值，然后在倒着来设af[a[j]]表示f(j,n,a[j])的值。

然后再用线段树更新一下长度为af[a[j]]的值然后再在树上查询小于be[a[j-1]]长度的一共有多少就行。

#include <iostream>

#include <cstring>

#include <map>

#include <cstdio>

using namespace std;

const int M = 1e6 + 10;

map<int , int>be , af;

int a[M];

struct TnT {

    int l , r , sum;

}T[M << 2];

void pushup(int i) {

    T[i].sum = T[i << 1].sum + T[(i << 1) | 1].sum;

}

void build(int l , int r , int i) {

    int mid = (l + r) >> 1;

    T[i].l = l , T[i].r = r , T[i].sum = 0;

    if(l == r) return ;

    build(l , mid , i << 1);

    build(mid + 1 , r , (i << 1) | 1);

    pushup(i);

}

void updata(int pos , int i) {

    int mid = (T[i].l + T[i].r) >> 1;

    if(T[i].l == T[i].r && T[i].l == pos) {

        T[i].sum++;

        return ;

    }

    if(mid < pos) {

        updata(pos , (i << 1) | 1);

    }

    else {

        updata(pos , i << 1);

    }

    pushup(i);

}

int query(int l , int r , int i) {

    int mid = (T[i].l + T[i].r) >> 1;

    if(T[i].l == l && T[i].r == r) {

        return T[i].sum;

    }

    pushup(i);

    if(mid < l) {

        return query(l , r , (i << 1) | 1);

    }

    else if(mid >= r) {

        return query(l , r , i << 1);

    }

    else {

        return query(l , mid , i << 1) + query(mid + 1 , r , (i << 1) | 1);

    }

}

int main() {

    int n;

    scanf("%d" , &n);

    be.clear() , af.clear();

    for(int i = 1 ; i <= n ; i++) {

        scanf("%d" , &a[i]);

        be[a[i]]++;

    }

    build(1 , n , 1);

    long long ans = 0;

    be[a[n]]--;

    for(int i = n - 1 ; i >= 1 ; i--) {

        af[a[i + 1]]++;

        updata(af[a[i + 1]] , 1);

        if(be[a[i]] > 1)

            ans += (long long)query(1 , be[a[i]] - 1 , 1);

        be[a[i]]--;

    }

    printf("%I64d\n" , ans);

    return 0;

}

巴特西

codeforces 459 D. Pashmak and Parmida's problem（思维+线段树）

最新文章

热门文章