自动搬运

查看原文

来自洛谷，原作者为

	IC0CI Huh

搬运于2025-08-24 22:36:16，当前版本为作者最后更新于2025-05-28 19:12:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面分析

要求实现两种操作，分别为区间加、区间差值加。

区间差值加（自己取的名字）：将区间中每相邻两个数的差值加一个数。

关于主要内容

考虑做两次差分。

因为差分本身的意义就是后一个元素减前一个元素，因此做两次差分就可以实现区间差值加。

操作 $R$ 区间加 1，操作 $R$ 区间减 1。

操作 $H$ 对 $[l,mid]$ 区间差值加 1，$[mid,r]$ 区间差值减 1。

操作 $H$ 对 $[l,mid]$ 区间差值减 1，$[mid,r]$ 区间差值加 1。

关于具体的操作范围对于区间是奇数长度和偶数长度进行判断就行了。（手模几下就出来了）

Code

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

int rd() //省略快读

const int N = 2e5 + 5;
int n;
int b[N];//差分数组

signed main()
{
    int n = rd(),q = rd();
    while(q--)
    {
        char c;
        cin >> c;
        int l = rd(),r = rd();
        if(c == 'R') b[l]++,b[l + 1]--,b[r + 1]--,b[r + 2]++;
        if(c == 'D') b[l]--,b[l + 1]++,b[r + 1]++,b[r + 2]--;
        if(c == 'H')
        {
            int mid = (l + r) >> 1;
            b[l]++,b[mid + 1]--;
            if((r - l + 1) % 2) b[mid + 1]--,b[r + 2]++;
            else b[mid + 2]--,b[r + 2]++;
        }
        if(c == 'V')
        {
            int mid = (l + r) >> 1;
            b[l]--,b[mid + 1]++;
            if((r - l + 1) % 2) b[mid + 1]++,b[r + 2]--;
            else b[mid + 2]++,b[r + 2]--;
        }
    }
    for(int i = 1;i <= n;i++) b[i] += b[i - 1];
    for(int i = 1;i <= n;i++) b[i] += b[i - 1];
    for(int i = 1;i <= n;i++) cout << b[i] << '\n';
    return 0;
}

样例解释中的关于奇偶的判断似乎反了