前缀和

2055. 蜡烛之间的盘子 - 力扣（LeetCode）

其实只需要计算 每次查询的最前面的蜡烛和最后面的蜡烛 中间的盘子的数量 盘子的数量可以用前缀和来处理 （因为要频繁地查询 不能每次都数一遍 要直接用前缀和来求）

蜡烛的位置可以用二分查找来计算

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& q) 
    {
        vector<int>qzh(s.size() + 1, 0);
        vector<int>ans(q.size(), 0);
        vector<int>lz;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '|')lz.push_back(i);
            qzh[i + 1] = qzh[i] + (s[i] == '*');
        }
        if (lz.empty())return ans;
        for (int i = 0; i < q.size(); i++)
        {
            int a = q[i][0], b = q[i][1];
            int c = -1, d = -1;
            int l = 0, r = lz.size() - 1;
            
            while (l < r)
            {
                int mid = l + r >> 1;
                if (mid >= a) r = mid;
                else l = mid + 1;
            }
            if(lz[r] >= a)c = lz[r];
            else continue;
            
            l = 0, r = lz.size() - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (lz[mid] <= b) l = mid;
                else r = mid - 1;
            }
            if (lz[r] <= b) d = lz[r];
            else continue;

            if (c <= d) ans[i] = qzh[d + 1] - qzh[c];
        }
        return ans;
        }
    }
};

1236. 递增三元组 - AcWing题库

除了二分也可以用前缀和 比如b中的5 可以求出a中所有比5小的数 这时候就可以用哈希表＋前缀和 哈希表记录1 2 3 4 出现的次数 然后加起来 就可以得到比5小的数的个数

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], b[N], c[N], cnt1[N], cnt2[N], qzh1[N], qzh2[N];
int main()
{
    int n;
    cin>>n;
    
    for (int i = 1; i <= n; i++)
    {
        cin>>a[i];
        cnt1[++a[i]]++;
    }
    for (int i = 1; i <= n; i++)
    {
        cin>>b[i];
        b[i]++;
    }
    for (int i = 1; i <= n; i++)
    {
        cin>>c[i];
        cnt2[++c[i]]++;
    }
    qzh1[0] = cnt1[0];
    qzh2[0] = cnt2[0];
    for (int i = 1; i < N; i++)
    {
        qzh1[i] = qzh1[i - 1] + cnt1[i];
        qzh2[i] = qzh2[i - 1] + cnt2[i];
    }
    
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int k = b[i];
        ans += (long long)(qzh2[N - 1] - qzh2[k]) * qzh1[k - 1];
    }
    cout<<ans;
}