Submission #72560401

---

Source Code Expand

import sys
import string
import math
import bisect
import os
import heapq
import operator
from io import BytesIO, IOBase
from heapq import heappop,heappush
from functools import lru_cache,cache
from copy import copy,deepcopy
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations
from array import array


INF = float('inf')
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = sys.stdin.buffer.readline

ask = lambda *x:print('?',*x,flush=True)
reply = lambda *x:print('!',*x,flush=True)

RI = lambda: int(sys.stdin.readline())
RF = lambda: float(sys.stdin.readline())
RS = lambda: sys.stdin.readline().strip()
RFF = lambda: map(float, sys.stdin.readline().split())
RII = lambda: map(int, sys.stdin.readline().split())
RSS = lambda: map(str, sys.stdin.readline().strip().split())
RIL = lambda: list(RII())
RFL = lambda: list(RFF())
RSL = lambda: list(RSS())

from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break 
                    to = stack[-1].send(to)
            return to

    return wrappedfunc

class LazySegmentTree:
    def __init__(self, A):
        self.n = len(A)
        self.A = A
        self.N = self.n * 4
        self.S = [self.Node() for _ in range(self.N)]
        self.build(0, self.n - 1, 1)
    
    class Node:
        def __init__(self):
            """ 放默认值 """
            self.f = 0  # max
            self.g = 0  # count
            self.ll = 1
            self.l1 = 0
            self.l2 = False
    
    def modify_leaf(self, a: Node, i):
        """ 根据 A[i] 修改叶子 """
        a.f = self.A[i]
        
    def merge(self, a: Node,b: Node,c: Node):
        """ 将 b，c 的信息合并到 a """
        a.f = max(b.f,c.f)
        a.ll = b.ll+c.ll
        a.g = b.g+c.g
    
    def pushdown(self, a: Node,b: Node,c: Node):
        """ 将 a 的懒惰信息下传到 b，c """
        if a.l2==True:
            b.g = b.ll-b.g
            c.g = c.ll-c.g
            b.f = 0
            c.f = 0
            b.l1 = 0
            c.l1 = 0
            b.l2 = True
            c.l2 = True
            a.l2 = False
        if a.l1!=0:
            b.l1 += a.l1
            c.l1 += a.l1
            if b.g!=b.ll:
                b.f += a.l1
            if c.g!=c.ll:
                c.f += a.l1
            a.l1 = 0
    
    def build(self, l, r, p):
        if l == r:
            self.modify_leaf(self.S[p], l)
            return
        m = (l + r) >> 1
        self.build(l, m, p << 1)
        self.build(m + 1, r, p << 1 | 1)
        self.merge(self.S[p], self.S[p << 1], self.S[p << 1 | 1])
    
    def update1(self ,x, y, val):
        """ 更新位置 [x,y] 的节点 """
        if x>y:
            return
        self._update1(x, y, 0, self.n-1, 1, val)
    
    def _update1(self, x, y, l, r, p:int, val):
        if r-l+1>=2:
            self.pushdown(self.S[p], self.S[p << 1], self.S[p << 1 | 1])
            m = (l + r) >> 1
            pp = p<<1
            if m-l+1>=2:
                self.pushdown(self.S[pp], self.S[pp << 1], self.S[pp << 1 | 1])
            pp = p<<1|1
            if r-(m+1)+1>=2:
                self.pushdown(self.S[pp], self.S[pp << 1], self.S[pp << 1 | 1])
        if x <= l and y >= r:
            """ 这里写相应的区间修改 """
            if self.S[p].g<self.S[p].ll:
                self.S[p].f += val
                self.S[p].l1 += val
            return
        m = (l + r) >> 1
        if x <= m:
            self._update1(x, y, l, m, p << 1, val)
        if y >= m + 1:
            self._update1(x, y, m + 1, r, p << 1 | 1, val)
        self.merge(self.S[p], self.S[p << 1], self.S[p << 1 | 1])

    def update2(self ,x, y):
        """ 更新位置 [x,y] 的节点 """
        if x>y:
            return
        self._update2(x, y, 0, self.n-1, 1)
    
    def _update2(self, x, y, l, r, p:int):
        if r-l+1>=2:
            self.pushdown(self.S[p], self.S[p << 1], self.S[p << 1 | 1])
            m = (l + r) >> 1
            pp = p<<1
            if m-l+1>=2:
                self.pushdown(self.S[pp], self.S[pp << 1], self.S[pp << 1 | 1])
            pp = p<<1|1
            if r-(m+1)+1>=2:
                self.pushdown(self.S[pp], self.S[pp << 1], self.S[pp << 1 | 1])
        if x <= l and y >= r:
            """ 这里写相应的区间修改 """
            self.S[p].g = self.S[p].ll-self.S[p].g
            self.S[p].l2 = True
            self.S[p].l1 = 0
            self.S[p].f = 0
            return
        m = (l + r) >> 1
        if x <= m:
            self._update2(x, y, l, m, p << 1)
        if y >= m + 1:
            self._update2(x, y, m + 1, r, p << 1 | 1)
        self.merge(self.S[p], self.S[p << 1], self.S[p << 1 | 1])

    def query(self, x, y):
        """ 查询区间[x, y]的信息 """
        return self._query(x,y,0,self.n-1,1)
    
    def _query(self, x, y, l, r, p):
        if x <= l and y >= r:
            return self.S[p]
        
        m = (l + r) >> 1
        self.pushdown(self.S[p], self.S[p << 1], self.S[p << 1 | 1])
        b = self.Node()
        c = self.Node()
        if x <= m:
            b = self._query(x, y, l, m, p << 1)
        if y >= m + 1:
            c = self._query(x, y, m + 1, r, p << 1 | 1)
        
        a = self.Node()
        self.merge(a, b, c)
        return a

def main():
    n,q = RII()
    
    a = [0]*(n+1)
    
    d = LazySegmentTree(a)
    
    for _ in range(q):
        inp = RIL()
        
        if inp[0]==1:
            l,r,x = inp[1:]
            l -= 1
            r -= 1
            d.update1(l,r,x)
        if inp[0]==2:
            l,r = inp[1:]
            l -= 1
            r -= 1
            d.update2(l,r)
        if inp[0]==3:
            l,r = inp[1:]
            l -= 1
            r -= 1
            ans = d.query(l,r).f
            print(ans)
    
if __name__ == '__main__':
    main()

                

Submission Info

Judge Result