题解：P13724 [GCPC 2024] Interference

yytmcjs · 2025-08-22 23:20:26 · 题解

P13724 [GCPC 2024] Interference

题目概括

在水槽内有一些波，每列波的波长都为四，且第一个正波峰都在波的区间的第一个位置。每个位置上的波高度会相加。有 n 次操作，每次给出两种操作其中一种：

• 当输入为 ! 时，描述一个波的起始位置 p、长度 l 与振幅 a（振幅就是波的高度）。
• 当输入为 ? 时，给定一个点，查询在此点上的波（相加）的高度。

  思路

  注意到，水池的宽度最长可达到 10^9，显然，每次遍历每个点修改是不可行的，于是我们想到记录每个波的参数，在查询时遍历每个波，计算其贡献。

同时我们观察到，因为每个波峰之间的距离都为四，所以从波的一个波峰走向相邻的波谷时，中间只会经过一个整点，那便是波高度为零的时候。

所以不难得出结论：每个波只在其波峰与波谷时取到有价值的整点，也就是当其偏移起始位置的长度 len \bmod 4 = 1 或 len \bmod 4 = 3 时。

实现思路

1. 在每次读入波的参数时记录在一个结构体数组中。
2. 对于每次询问 P，遍历数组中每个波，如果 P 不在当前波的范围内，跳过遍历下一个。
3. 每找到一个可行的波，计算 P 对于这个波起始位置的偏移量 len，然后对 4 取模，余 1 则当前点的答案 ans 加上波的波峰高度 a，余 3 则减去，否则不变。
4. 输出答案。

顺便提一嘴，因为每个询问都保证在水池宽度以内，所以读入的水池宽度没有任何用处。

代码

#include <bits/stdc++.h>
using namespace std;

struct wave{        //记录每个波的参数 
    int p,l;
    long long a;
}w[10005];

int n,W,tot;

int main(){
    cin >> n >> W;      //读入 
    for (int i=1;i<=n;i++){
        char op;
        cin >> op;
        if (op=='!'){       //将波的参数读入 
            int p,l;
            long long a;
            cin >> p >> l >> a;
            w[++tot].p=p;
            w[tot].l=l;
            w[tot].a=a;
        }
        else{
            int P;
            cin >> P;
            long long ans=0;
            for (int i=1;i<=tot;i++){       //遍历每个波 
                wave x=w[i];
                if (P<x.p || P>x.p+x.l-1) continue;     //不在范围内 
                int len=P-x.p+1;        //偏移量 
                if (len%4==1)       //在波峰上 
                    ans+=x.a;
                else if (len%4==3)      //在波谷上 
                    ans-=x.a;
            }
            cout << ans << endl;        //输出 
        }
    }
    return 0;
}