题解：P14598 [COCI 2025/2026 #2] 搭塔 / Tornjevi

· · 题解

这么典的莫队怎么能不写呢？

思路

首先因为第 i 块积木的边长为 i，所以整个序列的边长的递增的，于是你边长严格递减和严格递增是一样的，那我们正着做就行了。

发现一座塔肯定是形如 cpcpcp... 或者 pcpcpc... 的，于是考虑经典的括号序列匹配，将在同一座塔的点都染上相同的颜色。然后对询问就是区间数颜色了。

具体的，我们开两个栈维护未匹配的 P 和 C 的位置，然后遇到一个 P 我们就在 C 的栈里匹配，C 就在 P 的栈里匹配，将在同一个块的点都染上相同的颜色。

Code

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e05 + 700;
int n, m, tot;
int ans[MAXN], sum, cnt[MAXN];
char s[MAXN];
int a[MAXN], bel[MAXN];
stack <int> stp, stc;
struct qes {
    int l, r, id;
} q[MAXN];
void init(int n)
{
    int siz = sqrt(n), num = n / siz + 1;
    for(int i = 1; i <= num; i++)
    {
        for(int j = (i - 1) * siz + 1; j <= i * siz; j++)
            bel[j] = i;
    }
    return ;
}
bool cmp(qes a, qes b)
{
    return (bel[a.l] ^ bel[b.l]) ? bel[a.l] < bel[b.l] : ((bel[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
inline void add(int x)
{
    if(!cnt[a[x]])
        ++sum;
    cnt[a[x]]++;
    return ;
}
inline void del(int x)
{
    --cnt[a[x]];
    if(!cnt[a[x]])
        --sum;
    return ;
}
signed main()
{
    scanf("%d%d", &n, &m), scanf("%s", s + 1);
    init(n);
    for(int i = 1; i <= n; i++)
    {
        if(s[i] == 'P')
        {
            stp.push(i);
            if(stc.size())
                a[i] = a[stc.top()], stc.pop();
            else
                a[i] = ++tot;
        }
        else
        {
            stc.push(i);
            if(stp.size())
                a[i] = a[stp.top()], stp.pop();
            else
                a[i] = ++tot;
        }
    }
    for(int i = 1; i <= m; i++)
        scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    sort(q + 1, q + m + 1, cmp);
    int l = 1, r = 0;
    for(int i = 1; i <= m; i++)
    {
        while(l < q[i].l)
            del(l++);
        while(l > q[i].l)
            add(--l);
        while(r < q[i].r)
            add(++r);
        while(r > q[i].r)
            del(r--);
        ans[q[i].id] = sum;
    }
    for(int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}