摘要
Title: Acwing 第 43 场周赛
Tag: 不等式、树状数组、离散化

Acwing 第 43 场周赛

A AcWing 4314. 三元组

题意

请你计算共有多少个整数三元组 (a,b,c) 能够同时满足：
1≤a≤b≤c≤n。
a⊕b⊕c=0，其中 ⊕ 表示按位异或。
(a,b,c) 可以构成一个非退化三角形（即任意两边之和均大于第三边）。
思路

模拟

代码

n = int(input())
ans = 0
for a in range(1, n + 1):
    for b in range(a, n + 1):
        for c in range(b, n + 1):
            if a ^ b ^ c == 0:
                if a + b > c and a + c > b and b + c > a:
                    ans += 1
print(ans)

B AcWing 4315. 两个数列

题意

见原题
思路

求出 $b[i]$ 的上界和下界 $[bound, up]$ ，然后和其原上界和下界 $[1，a[i]]$ 求不等式交集

代码

'''
Author: NEFU AB-IN
Date: 2022-03-19 18:54:01
FilePath: \ACM\Acwing\43\b.py
LastEditTime: 2022-03-20 10:44:03
'''
n, s = map(int, input().split())

a = list(map(int, input().split()))
sum = sum(a)


def get(l1, r1, l2, r2):
    return min(r1, r2) - max(l1, l2) + 1


for i in range(n):
    l1, r1 = 1, a[i]
    l2 = s - (sum - a[i])
    r2 = s - (n - 1)

    ans = get(l1, r1, l2, r2)
    print(a[i] - ans, end=" ")

C AcWing 4316. 合适数对

题意

给定一个长度为 n 的整数数列 a1,a2,…,an 和一个整数 t。
请你判断共有多少个数对 (l,r) 同时满足：
1≤l≤r≤n
al+al+1+…+ar−1+ar<t
思路

由于 $a_i$ 的值是存在负数的，所以不能保证前缀和是递增的，所以需要用到树状数组求乱序动态的前缀和

ps：
- 离散化，即把所有能用到的值都放到离散化数组xs中
- 假设i是右端点，j是左端点，所以思路就是枚举每个右端点i， $S_{j - 1} > S_i - t$ ，在树状数组中查询，此时符合条件的j
- 而 $0 <= j - 1 <= i - 1 , 1 <= i <= n$ , 所以 $S_0$ 也会被用到

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-03-19 19:59:50
* @FilePath: \ACM\Acwing\43\c.cpp
* @LastEditTime: 2022-03-19 23:16:31
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;
const LL INF = 0x3f3f3f3f3f3f3f3f;

#define lowbit(x) x & -x

const int N = 4e5 + 20;
LL tr[N], s[N], n, t;
vector<LL> xs(1, -INF); // 树状数组离散化的下标从1开始，我习惯上设置一个哨兵
LL ans;

void add(int x, int v)
{
    for (int i = x; i < N; i += lowbit(i))
    {
        tr[i] += v;
    }
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
    {
        res += tr[i];
    }
    return res;
}

int get(LL x)
{
    return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
}

signed main()
{
    scanf("%lld%lld", &n, &t);
    for (int i = 1; i <= n; ++i)
    {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    for (int i = 1; i <= n; ++i)
    { // 0 <= j - 1 <= i - 1 , 1 <= i <= n
        xs.push_back(s[i]);
        xs.push_back(s[i] - t);
    }
    xs.push_back(0);
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());

    add(get(s[0]), 1); // 先把S_0加进去
    for (int i = 1; i <= n; ++i)
    {
        ans += i - query(get(s[i] - t)); // 目前的总和 - 小于等于自己的
        add(get(s[i]), 1);
    }
    printf("%lld\n", ans);
    return 0;
}

Acwing 第 43 场周赛

A AcWing 4314. 三元组

题意

思路

代码

B AcWing 4315. 两个数列

题意

思路

代码

C AcWing 4316. 合适数对

题意

思路

代码