跳转至

ABC342(A-G)

A - Yay!

题目大意

给你一个字符串 \(S(3 \le |S| \le 100)\)，除了有一个字符不同以外，其他字符都相同。找出那个与不同的字符的位置。

参考代码 
#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;
    int n = s.length();
    if(s[0] == s[1]) {
        for(int i = 2; i < n; i++)
            if(s[i] != s[0])
            {
                cout << i + 1;
                break;
            }
    }
    else
        cout << (s[0] == s[2] ? 2 : 1);
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int n = s.length();
        if (s.charAt(0) == s.charAt(1)) {
            for (int i = 2; i < n; i++)
                if (s.charAt(i) != s.charAt(0)) {
                    System.out.println(i + 1);
                    break;
                }
        } else
            System.out.println(s.charAt(0) == s.charAt(2) ? 2 : 1);
        in.close();
    }
}

B - Which is ahead?

题目大意

有 \(N\) 个人站成一排，第 \(i\) 个位置是编号为 \(A_i\) 的人。有 \(Q\) 个询问，询问给你两个编号 \(A_i\) 和 \(B_i\)，回答哪个人更靠左。

参考代码 
#include <iostream>

using namespace std;

const int maxn = 100 + 10;
int n, p[maxn];

int main()
{
    cin >> n;
    for(int i = 1, x; i <= n; i++)
        cin >> x, p[x] = i;
    int q, a, b;
    cin >> q;
    while(q--)
    {
        cin >> a >> b;
        cout << (p[a] < p[b] ? a : b) << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] p = new int[n + 1];
        for (int i = 1, x; i <= n; i++) {
            x = in.nextInt();
            p[x] = i;
        }
        int q, a, b;
        q = in.nextInt();
        while (q-- > 0) {
            a = in.nextInt();
            b = in.nextInt();
            System.out.println(p[a] < p[b] ? a : b);
        }
        in.close();
    }
}

C - Many Replacement

题目大意

给你一个字符串长度为 \(N(N \le 2 \times 10^5)\) 的字符串 \(S\)， \(S\) 中只有小写英文字母。同时执行 \(Q(Q \le 2 \times 10^5)\) 次操作，每次操作包括两个字符 \(c_i\) 和 \(d_i\) 表示将字符串 \(S\) 的所有字符 \(c_i\) 替换成 \(d_i\)。输出所有操作结束之后的字符串 \(S\)。

解题思路

开一个数组来表示每个字符的映射关系，p[c] == d 表示字符 \(c\) 映射成字符 \(d\)，修改的时候将所有 p[i] == c 的位置改成 d 即可。时间复杂度 \(O(26 \times(N+Q))\)。

想了一下应该没有 \(O(N+Q)\) 的做法......

参考代码 
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 2E5 + 10;
int n, q, p[30];
char s[maxn];

int main()
{
    for(int i = 0; i < 26; i++)
        p[i] = i;
    cin >> n;
    scanf("%s", s);
    cin >> q;
    while(q--) 
    {
        char c[2], d[2];
        scanf("%s %s", c, d);
        for(int i = 0; i < 26; i++)
            if(p[i] == c[0]-'a')
                p[i] = d[0] - 'a';
    }
    for(int i = 0; i < n; i++)
        printf("%c", p[s[i]-'a']+'a');
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n, q;
        int[] p = new int[26];
        String s;
        for (int i = 0; i < 26; i++)
            p[i] = i;
        n = in.nextInt();
        s = in.next();
        q = in.nextInt();
        while (q-- > 0) {
            String c, d;
            c = in.next();
            d = in.next();
            for (int i = 0; i < 26; i++)
                if (p[i] == c.charAt(0) - 'a')
                    p[i] = d.charAt(0) - 'a';
        }
        for (int i = 0; i < n; i++)
            System.out.printf("%c", p[s.charAt(i) - 'a'] + 'a');
        in.close();
    }
}

D - Square Pair

题目大意

给你 \(N(N \le 2 \times 10^5)\) 个数，第 \(i\) 个数是 \(A_i(0 \le A_i \le 2 \times 10^5)\)，求出满足下列要求的数对 \((i, j)\) 的个数：

  • \(1 \le i < j \le N\)
  • \(A_iA_j\) 是完全平方数。
解题思路

对每个数质因数分解，留下指数为奇数的部分，存入哈希表即可。特别的要注意 \(A_i = 0\) 的情形，需要直接加。

参考代码 
#include <iostream>
#include <cstdio>
#include <unordered_map>

using namespace std;

typedef long long LL;

int divide(int x)
{
    int ans = 1;
    for(int i = 2; i * i <= x; i++)
    {
        if(x % i == 0)
        {
            int c = 0;
            while(x % i == 0)
            {
                x /= i;
                c ^= 1;
            }
            if(c)
                ans *= i;
        }
    }
    if(x != 1)
        ans *= x;
    return ans;
}

int main()
{
    unordered_map<int, int> cnt;
    int n, z = 0;
    cin >> n;
    LL ans = 0;
    for(int i = 0, x; i < n; i++)
    {
        scanf("%d", &x);
        if(x == 0)
        {
            z++;
            ans += n - z;
            continue;
        }
        x = divide(x);
        if(cnt.count(x))
        {
            ans += cnt[x];
            cnt[x]++;
        }
        else
            cnt[x] = 1;
    }
    cout << ans << endl;
    return 0;
}

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    private static int divide(int x) {
        int ans = 1;
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                int c = 0;
                while (x % i == 0) {
                    x /= i;
                    c ^= 1;
                }
                if (c == 1)
                    ans *= i;
            }
        }
        if (x != 1)
            ans *= x;
        return ans;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        HashMap<Integer, Integer> cnt = new HashMap<>();
        int n, z = 0;
        n = in.nextInt();
        long ans = 0;
        for (int i = 0, x; i < n; i++) {
            x = in.nextInt();
            if (x == 0) {
                z++;
                ans += n - z;
                continue;
            }
            x = divide(x);
            int k = cnt.getOrDefault(x, 0);
            ans += k;
            cnt.put(x, k + 1);
        }
        System.out.println(ans);
        in.close();
    }
}

E - Last Train

题目大意

有 \(N\) 个城市，每个城市都有一个火车站。给你 \(M(M \le 2 \times 10^5)\) 班火车的信息，每条信息可用六元组 \((l_i, d_i, k_i, c_i, A_i, B_i)\) 来表示，其含义是：在 \(l_i, l_i+d_i, l_i+2d_i, ...,l_i+(k_i-1)*d_i\) 这些时间点会有一辆从 \(A_i\) 开往 \(B_i\) 的火车，耗时 \(c_i\)。

第 \(N\) 个城市是最重要的城市，所有人都想去第 \(N\) 个城市，但是大家都不想尽早出发。你需要回答 \(N-1\) 个数字，表示对于 \(1 \le i \le N-1\) 城市的人来说，最晚什么时候从火车站出发，仍然可以到达第 \(N\) 个城市。如果第 \(i\) 个城市的人无论如何都不能到达第 \(N\)​​ 个城市，输出 Unreachable。

数据范围：

  • \(2 \le N \le 2 \times 10^5\)
  • \(1 \le M \le 2 \times 10^5\)
  • \(1 \le l_i, d_i, k_i, c_i \le 10^9(1 \le i \le M)\)
  • \(1 \le A_i, B_i \le N(1 \le i \le M)\)
  • \(A_i \neq B_i (1 \le i \le M)\)
  • 所有输入都是整数
解题思路

不妨设答案数组为 \(dis[i]\)，即第 \(i\) 个城市的人最晚在 \(dis[i]\) 的时刻出发仍然可以到达第 \(N\) 个城市。初始的时候有 \(dis[N] = \infty\)，因为已经在第 \(N\) 个点了。其他点的初始值设置为 \(0\)​。

目标就是最大化 \(dis[i]\) 的值，考虑如何更新，假设有边 \(u \rightarrow N\)，则只需要在这条边的末班车到达点 \(u\) 即可。同样的，假设 \(dis[v]\) 的值已经确定，且存在边 \(u \rightarrow v\)，不妨设这条边的耗时为 \(c\)，只需要在坐上 \(dis[v]-c\) 之前的最后一班车就能到达 \(N\)。于是不难想到从 N 开始倒着拓扑排序。

不过本题不一定是 DAG，所以不能拓扑。不过进一步发现两个点之间更新的边一定是负权边，这是因为 \(c > 0\)，并且我们要求的实际是最长路，所以实际这就是一个 dijkstra，不同的就是我们采用大顶堆，可以证明从大顶堆中取出来的点一定是已经确定的，不会再被更新的。

参考代码 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;
const int maxn = 2E5 + 10;
const LL inf = 0x3f3f3f3f3f3f3f3f;
int head[maxn], edge[maxn], ne[maxn], cost[maxn], interval[maxn], ft[maxn], cnt[maxn], idx = 1;
void add(int u, int v, int w, int l, int d, int k)
{
    edge[idx] = v;
    ne[idx] = head[u];
    cost[idx] = w;
    ft[idx] = l;
    interval[idx] = d;
    cnt[idx] = k;
    head[u] = idx++;
}

int n, m;
LL dis[maxn];

struct Node {
    int u;
    LL dis;
    Node(int _u, LL _d) : u(_u), dis(_d) {}
    bool operator < (const Node &y) const
    {return dis < y.dis;}
};

void dijkstra()
{
    dis[n] = inf;
    priority_queue<Node> heap;
    heap.push(Node(n, inf));
    while(!heap.empty()) 
    {
        Node p = heap.top();
        heap.pop();
        int u = p.u;
        if(p.dis != dis[u])
            continue;
        for(int i = head[u]; i; i = ne[i])
        {
            int v = edge[i];
            LL k = dis[u] - cost[i] - ft[i];
            if(k < 0)
                continue;
            k = min(k/interval[i], (LL)cnt[i]-1);
            LL nd = ft[i] + k * interval[i];
            if(nd > dis[v])
            {
                dis[v] = nd;
                heap.push(Node(v, nd));
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    while(m--)
    {
        int l, d, k, w, v, u;
        scanf("%d %d %d %d %d %d", &l, &d, &k, &w, &v, &u);
        add(u, v, w, l, d, k);
    }
    dijkstra();
    for(int i = 1; i < n; i++)
        if(!dis[i])
            puts("Unreachable");
        else
            printf("%lld\n", dis[i]);
    return 0;
}

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

class Node implements Comparable<Node> {
    public int u;
    public long dis;

    public Node(int _u, long _d) {
        u = _u;
        dis = _d;
    }

    public int compareTo(Node o) {
        return Long.compare(dis, o.dis);
    }
}

public class Main {
    private static final long inf = 0x3f3f3f3f3f3f3f3fl;
    private static int[] head, edge, ne, cost, interval, ft, cnt;
    private static long[] dis;
    private static int idx, n, m;

    private static void dijkstra() {
        dis[n] = inf;
        PriorityQueue<Node> heap = new PriorityQueue<>(Collections.reverseOrder());
        heap.add(new Node(n, inf));
        while (!heap.isEmpty()) {
            Node p = heap.remove();
            int u = p.u;
            if (p.dis != dis[u])
                continue;
            for (int i = head[u]; i > 0; i = ne[i]) {
                int v = edge[i];
                long k = dis[u] - cost[i] - ft[i];
                if (k < 0)
                    continue;
                k = Math.min(k / interval[i], (long) cnt[i] - 1);
                long nd = ft[i] + k * interval[i];
                if (nd > dis[v]) {
                    dis[v] = nd;
                    heap.add(new Node(v, nd));
                }
            }
        }
    }

    private static void graph_init(int n, int m) {
        idx = 1;
        head = new int[n];
        dis = new long[n];
        edge = new int[m];
        ne = new int[m];
        interval = new int[m];
        ft = new int[m];
        cnt = new int[m];
        cost = new int[m];
    }

    private static void add(int u, int v, int w, int l, int d, int k) {
        edge[idx] = v;
        ne[idx] = head[u];
        cost[idx] = w;
        ft[idx] = l;
        interval[idx] = d;
        cnt[idx] = k;
        head[u] = idx++;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        graph_init(n + 1, m + 1);
        while (m-- > 0) {
            int l, d, k, w, v, u;
            l = in.nextInt();
            d = in.nextInt();
            k = in.nextInt();
            w = in.nextInt();
            v = in.nextInt();
            u = in.nextInt();
            add(u, v, w, l, d, k);
        }
        dijkstra();
        for (int i = 1; i < n; i++)
            if (dis[i] == 0)
                System.out.println("Unreachable");
            else
                System.out.println(dis[i]);
        in.close();
    }
}

F - Black Jack

题目大意

有一个 \(D\) 个面的骰子，每个面都是等概率的。你正在和庄家玩一个游戏，游戏的流程为：

  • 你可以丢任意次骰子，你的权值就是你的所有结果的和，你的权值用 \(x\) 表示。
  • 在你结束投掷之后，庄家开始投掷，庄家的权值就是他投掷结果的和，庄家的权值用 \(y\) 表示。庄家的投掷规则是：当 \(y < L\) 时，继续投掷。当 \(y \ge L\) 时，停止投掷。

你的获胜方式为：

  1. \(x \le N\) 且 \(x > y\)
  2. \(x \le N\) 且 \(y > N\)

问：如果你使用最佳策略，获胜的概率有多少？

数据范围

  • \(1 \le L \le N \le 2 \times 10^5\)

  • \(1 \le D \le N\)

解题思路

要注意庄家会在 \(y > L\) 的时候就停止投掷，所以庄家的流程是固定的，是没有任何策略的。因此可以预处理一个数组 \(fy[i]\) 表示庄家投掷出 \(y = i\) 的概率。可以用 dp 的后向更新求出来：初始的时候有 \(f[0] = 1\)，则转移式为：\(fy[i+j] += fy[i] * \frac{1}{D}, 1 \le j \le D\)，不过这个式子的时间复杂度是 \(O(LD)\) 的，会超时。进一步会发现这就是一个区间加，差分一下就好了。

差分之后把前缀和处理出来，后面有用。

p = 1.0 / D;
fy[1] = p;
fy[D+1] = -p;
for(int i = 1; i < L; i++) // [1, L) 的区间必须投掷，所以要带上 fy[i] 的概率
{
    fy[i] += fy[i-1];
    fy[i+1] += fy[i] * p;
    fy[i+D+1] -= fy[i] * p;
}
for(int i = L; i <= N + D; i++) // [L, N+D] 区间不能投掷，只处理差分就好
    fy[i] += fy[i-1];
for(int i = L; i <= N + D; i++) // 前缀和
        fy[i] += fy[i-1];

接下来考虑我们的策略问题，不妨设 \(dp[i]\) 为当前 \(x = i(i \le N)\) 的时候我们获胜的概率，在这种情况下，我们只有两种决策：投掷或停止。先考虑停止，设 \(getsum(l, r)\) 表示 \(fy\) 数组的区间和，\(cal(i)\) 为 \(x = i\) 时停止我们能获胜的概率，则有：

\[ cal(i) = \left\{ \begin{matrix} getsum(N+1, N+D), & i < L \\ 1 - getsum(x, N), & i \ge L \end{matrix} \right. \]

这个式子是很直观的，因为如果我们在 \(i < L\) 的时候停止，只能希望庄家的值超过 \(N\)，这样才能获胜，而如果 \(i \ge L\)，只要庄家的值不是 \([x, N]\)，我们都能获胜。

进一步考虑另一种决策：投掷。则投掷之后的值可能是 \(i+1, i+2, ...,i+D\)，这些情况获胜的概率都要加起来，也就是 \(\frac{1}{D}\sum\limits_{j= 1}^D dp[i+j]\)。

因为我们是最佳策略，所以两者取较大值，即：

\[ dp[i] = \max\{\frac{1}{D}\sum\limits_{j= 1}^D dp[i+j], cal(i)\} \]

在处理出 \(fy\) 的前缀和之后， \(cal(i)\) 的计算是 \(O(1)\) 的。而 \(\frac{1}{D}\sum\limits_{j= 1}^D dp[i+j]\) 可以从后往前计算，同时维护一个滑动窗口，同样是 \(O(1)\) 的。

因此总的时间复杂度就是 \(O(N+D)\) 的。计算完成后 \(dp[0]\) 就是答案。

参考代码 
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 4E5 + 10;
double dp[maxn], p, fy[maxn];
int N, L, D;

double getsum(int l, int r)
{return fy[r] - fy[l-1];}

double cal(int x)
{
    if(x < L)
        return getsum(N+1, N+D);
    return 1 - getsum(x, N);
}

int main()
{
    cin >> N >> L >> D;
    p = 1.0 / D;
    fy[1] = p;
    fy[D+1] = -p;
    for(int i = 1; i < L; i++)
    {
        fy[i] += fy[i-1];
        fy[i+1] += fy[i] * p;
        fy[i+D+1] -= fy[i] * p;
    }
    for(int i = L; i <= N + D; i++)
        fy[i] += fy[i-1];
    for(int i = L; i <= N + D; i++)
        fy[i] += fy[i-1];
    double sum = 0;
    for(int i = N, r = i + D; i >= 0; sum += dp[i--] - dp[r--])
        dp[i] = max(sum*p, cal(i));
    printf("%.8lf", dp[0]);
    return 0;
}

import java.util.Scanner;

public class Main {
    private static double[] fy;
    private static int N, L, D;

    private static double getsum(int l, int r) {
        return fy[r] - fy[l - 1];
    }

    private static double cal(int x) {
        if (x < L)
            return getsum(N + 1, N + D);
        return 1 - getsum(x, N);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        L = in.nextInt();
        D = in.nextInt();
        fy = new double[N + D + 1];
        double[] dp = new double[N + D + 1];
        double p = 1.0 / D;
        fy[1] = p;
        fy[D + 1] = -p;
        for (int i = 1; i < L; i++) {
            fy[i] += fy[i - 1];
            fy[i + 1] += fy[i] * p;
            fy[i + D + 1] -= fy[i] * p;
        }
        for (int i = L; i <= N + D; i++)
            fy[i] += fy[i - 1];
        for (int i = L; i <= N + D; i++)
            fy[i] += fy[i - 1];
        double sum = 0;
        for (int i = N, r = i + D; i >= 0; sum += dp[i--] - dp[r--])
            dp[i] = Math.max(sum * p, cal(i));
        System.out.printf("%.8f\n", dp[0]);
        in.close();
    }
}

G - Retroactive Range Chmax

题目大意

维护一个 \(N(N \le 2 \times 10^5)\) 个数的数列，初始的时候数列的第 \(i\) 个数是 \(A_i\)，有 \(Q(Q \le 2 \times 10^5)\) 个操作：

  • \(1 \ l_i, r_i, x_i\)：表示将区间 \([l_i, r_i]\) 中的每个 \(A_i\) 替换为 \(\max(A_i, x)\)。
  • \(2 \ i\)：表示撤销第 \(i\) 个操作。保证第 \(i\) 次操作的类型是 \(1\)，且未被撤销。
  • \(3 \ i\)：查询 \(A_i\) 的值。
解题思路

区间改，肯定要用懒标记的线段树，只不过由于涉及到撤销操作，所以懒标记不能只存一个。

用 multiset 存储所有这个区间涉及到的懒标记，查询的时候查的就是 multiset 里面的最大值，需要带上区间的懒标记一起输出，删除的时候也是一起删除。

由于用了懒标记，每次操作最多增加 \(logN\) 个点，因此空间复杂度是 \(O(QlogN)\)，单次查询除了在线段树里面找，还需要在红黑树里面找最大，所以单次查询需要的时间复杂度是 \(O(log^2N)\)

参考代码 
#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

const int maxn = 2E5 + 10;
int n, m, a[maxn];
multiset<int> t[maxn * 4];

struct Query {
    int l, r, x;
}q[maxn];

void build(int p, int beg, int end)
{
    if(beg == end)
    {
        t[p].insert(a[beg]);
        return;
    }
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = p * 2 + 1;
    build(lch, beg, mid);
    build(rch, mid+1, end);
}

void update(int p, int beg, int end, int l, int r, int x)
{
    if(end < l || beg > r)
        return;
    if(beg >= l && end <= r)
    {
        t[p].insert(x);
        return;
    }
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = p * 2 + 1;
    update(lch, beg, mid, l, r, x);
    update(rch, mid+1, end, l, r, x);
}

int ask(int p, int beg, int end, int pos)
{
    if(end < pos || beg > pos)
        return 0;
    if(beg == end)
        return *t[p].rbegin();
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = p * 2 + 1;
    int ans = t[p].empty() ? 0 : *t[p].rbegin();
    return max(ans, pos <= mid ? ask(lch, beg, mid, pos) : ask(rch, mid+1, end, pos));
}

void del(int p, int beg, int end, int l, int r, int x)
{
    if(end < l || beg > r)
        return;
    if(beg >= l && end <= r)
    {
        t[p].erase(t[p].find(x));
        return;
    }
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = p * 2 + 1;
    del(lch, beg, mid, l, r, x);
    del(rch, mid+1, end, l, r, x);
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        int op, x, j;
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d %d %d", &q[i].l, &q[i].r, &q[i].x);
            update(1, 1, n, q[i].l, q[i].r, q[i].x);
        }
        else if(op == 2)
        {
            scanf("%d", &j);
            del(1, 1, n, q[j].l, q[j].r, q[j].x);
        }
        else 
        {
            scanf("%d", &x);
            printf("%d\n", ask(1, 1, n, x));
        }
    }
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
    static FastReader in = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    private static TreeMap<Integer, Integer>[] t;
    private static int[] a;

    private static void build(int p, int beg, int end) {
        t[p] = new TreeMap<>();
        if (beg == end) {
            t[p].put(a[beg], 1);
            return;
        }
        int mid = (beg + end) / 2;
        int lch = p * 2, rch = p * 2 + 1;
        build(lch, beg, mid);
        build(rch, mid + 1, end);
    }

    private static void update(int p, int beg, int end, int l, int r, int x) {
        if (end < l || beg > r)
            return;
        if (beg >= l && end <= r) {
            t[p].put(x, t[p].getOrDefault(x, 0) + 1);
            return;
        }
        int mid = (beg + end) / 2;
        int lch = p * 2, rch = p * 2 + 1;
        update(lch, beg, mid, l, r, x);
        update(rch, mid + 1, end, l, r, x);
    }

    private static int ask(int p, int beg, int end, int pos) {
        if (end < pos || beg > pos)
            return 0;
        if (beg == end)
            return t[p].lastKey();
        int mid = (beg + end) / 2;
        int lch = p * 2, rch = p * 2 + 1;
        int ans = t[p].isEmpty() ? 0 : t[p].lastKey();
        return Math.max(ans, pos <= mid ? ask(lch, beg, mid, pos) : ask(rch, mid + 1, end, pos));
    }

    private static void del(int p, int beg, int end, int l, int r, int x) {
        if (end < l || beg > r)
            return;
        if (beg >= l && end <= r) {
            int z = t[p].get(x);
            if (z == 1)
                t[p].remove(x);
            else
                t[p].put(x, z - 1);
            return;
        }
        int mid = (beg + end) / 2;
        int lch = p * 2, rch = p * 2 + 1;
        del(lch, beg, mid, l, r, x);
        del(rch, mid + 1, end, l, r, x);
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        int n = in.nextInt();
        a = new int[n + 1];
        t = new TreeMap[4 * n];
        for (int i = 1; i <= n; i++)
            a[i] = in.nextInt();
        build(1, 1, n);
        int m = in.nextInt();
        int[] l = new int[m + 1];
        int[] r = new int[m + 1];
        int[] x = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            int op, id;
            op = in.nextInt();
            if (op == 1) {
                l[i] = in.nextInt();
                r[i] = in.nextInt();
                x[i] = in.nextInt();
                update(1, 1, n, l[i], r[i], x[i]);
            } else if (op == 2) {
                id = in.nextInt();
                del(1, 1, n, l[id], r[id], x[id]);
            } else {
                id = in.nextInt();
                out.println(ask(1, 1, n, id));
            }
        }
        out.flush();
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}
最后更新: 2024-07-26
创建日期: 2024-03-08