树状数组

前置知识树状数组https://oi-wiki.org/ds/fenwick/ $\\$ 对于目前的$i$只需要利用$map$映射$f(1,i,ai)$的值就可以知道也就是$mp[a[i]]$，怎么快速知道有多少个$f(j,n,aj)$小于$mp[a[i]]$,用一个树状数组维护，就可以直接区间查找了.$\\$ 具体做法 $add(f(j,n,aj),1),1<=j<=n$$\\$ 枚举$i$然后$add(f(i,n,ai),-1)$$ans+=query(1,f(i,n,ai)-1)$$\\$ 整体时间复杂度$o(nlog_2n)$ $\\$

代码如下

$cpp$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 200000
int t1[N];
int lowbit(int x) {
	return ((-x)&x);
}
void add(int x, int y) {
	for (int i = x; i < N; i += lowbit(i)) {
		t1[i] += y;
	}
}
int query(int r) {//f(j,n,aj)<=r
	int res = 0;
	for (int i = r; i; i -= lowbit(i)) {
		res += t1[i];
	}
	return res;
}
int a[N];
int suf[N];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	vector<char>c(27);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	map<int, int>mp;
	for (int i = n; i >= 1; i--) {
		mp[a[i]] += 1;
		suf[i] = mp[a[i]];
		add(suf[i], 1);
	}
	mp.clear();
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		mp[a[i]] += 1;//f(1,i,ai)
		add(suf[i], - 1);
		ans += query(mp[a[i]] - 1);
	}
	cout << ans << '\n';
}

$python$

def lowbit(x):
    return x & -x

def add(x, y, t1, N):
    while x < N:
        t1[x] += y
        x += lowbit(x)

def query(r, t1):
    res = 0
    while r > 0:
        res += t1[r]
        r -= lowbit(r)
    return res

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    a = list(map(int, data[1:n+1]))
    
    N = 200000
    t1 = [0] * N
    suf = [0] * (n + 1)
    mp = {}
    
    # Calculate suffix frequencies
    for i in range(n - 1, -1, -1):
        mp[a[i]] = mp.get(a[i], 0) + 1
        suf[i + 1] = mp[a[i]]
        add(suf[i + 1], 1, t1, N)
    
    mp.clear()
    ans = 0
    
    # Calculate the result
    for i in range(1, n + 1):
        mp[a[i - 1]] = mp.get(a[i - 1], 0) + 1
        add(suf[i], -1, t1, N)
        ans += query(mp[a[i - 1]] - 1, t1)
    
    print(ans)

if __name__ == "__main__":
    main()

$java$

import java.io.*;  
import java.util.*;  
  
public class Main {  
    static class Node {  
        long sum;  
        long pre;  
  
        Node(long sum, long pre) {  
            this.sum = sum;  
            this.pre = pre;  
        }  
    }  
  
    static class Pair<T, U> {  
        T first;  
        U second;  
  
        Pair(T first, U second) {  
            this.first = first;  
            this.second = second;  
        }  
    }  
  
    static Node merge(Node a, Node b) {  
        return new Node(a.sum + b.sum, Math.max(a.pre, a.sum + b.pre));  
    }  
  
    static Pair<Integer, Node>[][] f = new Pair[200005][31];  
    static long[] nxt = new long[200005];  
    static long[] a = new long[200005];  
    static int n, q;  
    static long x, y;  
  
    static void init() {  
        for (int i = 1; i <= n; i++) {  
            f[i][0] = new Pair<>((int) nxt[i], new Node(0, 0));  
            long w = a[(int) nxt[i]] > a[i] ? x : y;  
            f[i][0].second = new Node(w, w);  
        }  
  
        for (int i = 1; i < 30; i++) {  
            for (int j = 1; j <= n; j++) {  
                int v = f[j][i - 1].first;  
                f[j][i] = new Pair<>(f[v][i - 1].first, merge(f[j][i - 1].second, f[v][i - 1].second));  
            }  
        }  
    }  
  
    static long ask(int u, int k) {  
        Node r = new Node(0, 0);  
        for (int i = 29; i >= 0; i--) {  
            if ((k >> i & 1) == 1) {  
                r = merge(r, f[u][i].second);  
                u = f[u][i].first;  
            }  
        }  
        return r.pre;  
    }  
  
    /**
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {  
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();  
        q = scanner.nextInt();  
        x = scanner.nextInt();  
        y = scanner.nextInt();  
  
        for (int i = 1; i <= n; i++) {  
            nxt[i] = scanner.nextInt();  
          //  System.out.println(nxt[i]);
        }  
  
        for (int i = 1; i <= n; i++) {  
            a[i] = scanner.nextInt();  
        }  
  
        init();  
  
        while (q-- > 0) {  
            int u = scanner.nextInt();  
            int k = scanner.nextInt();  
            System.out.println(ask(u, k));  
        }  
    }  
}

题目内容

小明有一个长度为$n$的数组$a$，记$f(l,r,x)$为区间[$l,r$]内$x$的出现次数。

现在小明想知道有多少对$i<j$满足$f(1,i,a_i)>f(j,n,a_j)$。

输入描述

第一行输入一个整数 $n$

第二行$n$个整数$a_1,a_2,...,a_n$。

$1≤n≤10^5$

$1≤a_i≤10^9$

输出描述

输出一个整数表示答案。

样例1

输入

6
1 2 1 2 2 1

输出

5

说明

存在以下五对($i,j$)满足条件：$(3,5)(3,6)(4,5)(4,6)(5,6)$

样例2

输入

输出