题解

问题分析

题目要求高效处理两种操作：对数组区间执行累加取模（operate1）和统计区间内相邻元素的逆序对数（operate2）。核心挑战是在大规模数据（( n, m \leq 10^5 )）下，避免朴素模拟的 ( O(n) ) 单次操作复杂度，需通过数据结构优化。

关键思路

1. 核心观察：

   • operate2(l, r) 统计的是区间 ([l, r-1]) 中 ( a[i] > a[i+1] ) 的数量，即相邻逆序对。
   • operate1(l, r, c) 对区间元素累加 ( c \mod p )，这会影响相邻元素的大小关系（进而影响逆序对）。

2. 数据结构选择：
   使用 线段树 维护区间信息，每个节点存储：

   • 区间内相邻逆序对的总数（用于 operate2 查询）。
   • 区间左右端点的当前值（用于合并子区间时计算跨边界的逆序对）。
   • 懒标记（记录未生效的区间累加值，用于 operate1 高效更新）。

3. 线段树设计：

   • 节点结构：cnt（区间内逆序对总数）、left_val（区间左端点值）、right_val（区间右端点值）、lazy（累加懒标记）。
   • 区间更新：对 operate1，通过懒标记传递累加值，更新节点的 left_val、right_val，并标记子节点待更新。
   • 区间查询：对 operate2，合并子区间的 cnt 并加上跨边界的逆序对（通过左右子节点的 right_val 和 left_val 计算）。
   • 合并逻辑：父节点的 cnt = 左子树 cnt + 右子树 cnt +（左子树 right_val > 右子树 left_val ? 1 : 0）。

代码实现

import sys
MOD = None  # 全局取模常数

class SegmentTreeNode:
    __slots__ = ['l', 'r', 'left', 'right', 'cnt', 'left_val', 'right_val', 'lazy']
    def __init__(self, l, r):
        self.l = l  # 区间左端点（1-based）
        self.r = r  # 区间右端点（1-based）
        self.left = None  # 左子树
        self.right = None  # 右子树
        self.cnt = 0  # 区间内相邻逆序对数量
        self.left_val = 0  # 区间左端点值
        self.right_val = 0  # 区间右端点值
        self.lazy = 0  # 累加懒标记

    def push_down(self):
        """下传懒标记到子节点"""
        if self.lazy != 0 and self.left:
            # 更新左子树
            self.left.left_val = (self.left.left_val + self.lazy) % MOD
            self.left.right_val = (self.left.right_val + self.lazy) % MOD
            self.left.lazy = (self.left.lazy + self.lazy) % MOD
            # 更新右子树
            self.right.left_val = (self.right.left_val + self.lazy) % MOD
            self.right.right_val = (self.right.right_val + self.lazy) % MOD
            self.right.lazy = (self.right.lazy + self.lazy) % MOD
            # 清空当前节点懒标记
            self.lazy = 0

    def push_up(self):
        """从子节点更新当前节点信息"""
        self.left_val = self.left.left_val
        self.right_val = self.right.right_val
        # 逆序对总数 = 左子树cnt + 右子树cnt + 左右边界是否形成逆序对
        self.cnt = self.left.cnt + self.right.cnt
        if self.left.right_val > self.right.left_val:
            self.cnt += 1

def build(l, r, a):
    """构建线段树，a是1-based数组"""
    node = SegmentTreeNode(l, r)
    if l == r:
        # 叶子节点：无相邻元素，cnt=0，左右值均为a[l]
        node.left_val = a[l]
        node.right_val = a[l]
        node.cnt = 0
        return node
    mid = (l + r) // 2
    node.left = build(l, mid, a)
    node.right = build(mid + 1, r, a)
    node.push_up()
    return node

def update_range(node, l, r, c):
    """区间[l, r]累加c mod p"""
    if node.r < l or node.l > r:
        return
    if l <= node.l and node.r <= r:
        # 完全覆盖：更新当前节点的边界值和懒标记
        node.left_val = (node.left_val + c) % MOD
        node.right_val = (node.right_val + c) % MOD
        node.lazy = (node.lazy + c) % MOD
        return
    # 部分覆盖：下传懒标记后递归更新子树
    node.push_down()
    update_range(node.left, l, r, c)
    update_range(node.right, l, r, c)
    node.push_up()

def query_range(node, l, r):
    """查询区间[l, r-1]的逆序对数量（即[l, r)内相邻元素的逆序对）"""
    if node.r <= l or node.l >= r:
        return 0
    if l <= node.l and node.r < r:
        return node.cnt
    node.push_down()
    left_cnt = query_range(node.left, l, r)
    right_cnt = query_range(node.right, l, r)
    # 检查左右子树交界处是否在查询范围内，若在则需加跨边界的逆序对
    cross = 0
    if node.left.r >= l and node.right.l < r:
        if node.left.right_val > node.right.left_val:
            cross = 1
    return left_cnt + right_cnt + cross

def main():
    global MOD
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    m = int(input[ptr+1])
    MOD = int(input[ptr+2])
    ptr +=3
    # 读取初始数组（1-based）
    a = [0]*(n+2)  # a[1..n]
    for i in range(1, n+1):
        a[i] = int(input[ptr]) % MOD
        ptr +=1
    # 构建线段树
    root = build(1, n, a)
    # 处理m条命令
    for _ in range(m):
        cmd = input[ptr]
        ptr +=1
        if cmd == '1':
            l = int(input[ptr])
            r = int(input[ptr+1])
            c = int(input[ptr+2])
            ptr +=3
            c_mod = c % MOD
            update_range(root, l, r, c_mod)
        else:
            l = int(input[ptr])
            r = int(input[ptr+1])
            ptr +=2
            if l >= r:
                print(0)
            else:
                res = query_range(root, l, r)
                print(res)

if __name__ == "__main__":
    main()

复杂度分析

• 线段树构建：( O(n) )，需初始化每个节点的信息。
• 区间更新（operate1）：通过懒标记实现 ( O(\log n) ) 单次操作，避免遍历每个元素。
• 区间查询（operate2）：合并子区间信息，单次操作复杂度 ( O(\log n) )。
• 总复杂度：( O(n + m \log n) )，可高效处理 ( n, m \leq 10^5 ) 的数据范围。

该方法通过线段树和懒标记，完美平衡了更新与查询的效率，满足题目要求。