杂题

统计子矩阵
暴力$O(N^4)$ 。
枚举左右边界，用快指针作下边界，慢指针作上边界，维护区间和小于$k$ ，对于每个下边界$down$ 的贡献为$down-up+1$ 。
区间和可用前缀和$O(1)$ 获得。

递增三元组
双指针：三个数组排序后枚举$B$ ，一个指针$i$ 使$a[i]$ 是小于$b[j]$ 的最后一个 ，一个指针$k$ 使$c[k]$ 是大于$b[j]$ 的第一个，ans+=i*(n-k+1) 。
前缀和：枚举$B$ ，统计小于$B[i]$ 的$A$ 的个数和大于$B[i]$ 的$C$ 的个数。因为值域只有$1e5$ ，所以前缀和维护即可。

激光炸弹
二维前缀和，但数据范围很坑。

棋盘
二维异或。

import sys
sys.setrecursionlimit(11000)
input=lambda:sys.stdin.readline().strip()
write=lambda x:sys.stdout.write(str(x))

def solve():
    n,m=map(int,input().split())
    N=2010
    a=[[0]*N for i in range(N)]
    for i in range(m):
        x1,y1,x2,y2=map(int,input().split())
        a[x1][y1]=1-a[x1][y1]
        a[x1][y2+1]=1-a[x1][y2+1]
        a[x2+1][y1]=1-a[x2+1][y1]
        a[x2+1][y2+1]=1-a[x2+1][y2+1]
    for i in range(1,n+1):
        for j in range(1,n+1):
            a[i][j]^=a[i-1][j]^a[i][j-1]^a[i-1][j-1]
        for j in range(1,n+1):
            write(a[i][j])
        write('\n')

    return


test=1
# test=int(input())
for _ in range(test):
    solve()

技能升级
二分最小攻击力，使攻击次数大于等于$m$ 。
如果小于等于$m$ ，则可能还会存留一些次数，但不知道剩余这些次数的攻击力为多少。
但若大于等于$m$ ，则可能多出来一些次数，多出来的这些次数的攻击力必为二分出来的答案$l$ 。
如果以$1$ 为左边界，则要先判断是否有多的次数，再减去这些攻击力。
但如果以$0$ 为左边界，无脑减多出来的攻击力即可。

经典模型:多路归并

谦虚数字
给定一个质数集合$X$，定义丑数为质因子只由$X$ 中的数 构成(规定$1$ 也是丑数)。
每个丑数乘$X$ 中的某个数也是丑数。
定义$S_0$ 为丑数集合，$S_i$ 为$S_0$ 中的每个数乘集合$X$ 中的第$i$ 个数所得集合。
$S_0$ 中的每个数(除$1$ 以外)都可以在$S_1$ 到S_{\abs{X}} 找到。
也就是说$S_0$ (除$1$ 以外)是由$S_1$ 到S_{\abs{X}} 多路归并得到。

import sys
sys.setrecursionlimit(11000)
input=lambda:sys.stdin.readline().strip()
write=lambda x:sys.stdout.write(str(x))

from heapq import heapify,heappush,heappop

def solve():
    k,n=map(int,input().split())
    n+=1
    row=list(map(int,input().split()))
    col=[1]
    heap=[]
    for i in range(k):
        heap.append([row[i],i,0])
    heapify(heap)
    while len(col)<n:
        v,x,y=heappop(heap)
        col.append(v)
        heappush(heap,[row[x]*col[y+1],x,y+1])
        while heap[0][0]==v:
            nv,nx,ny=heappop(heap)
            heappush(heap,[row[nx]*col[ny+1],nx,ny+1])
    print(col[n-1])
    return

test=1
# test=int(input())
for _ in range(test):
    solve()

序列
先考虑两路归并。
将$a$ 和$b$ 数组归并。
b\a |a[0] |a[1] |a[2] |a[3] |a[4]
b[0] |a[0]+b[0] |a[1]+b[0] |a[2]+b[0] |a[3]+b[0] |a[4]+b[0]
b[1] |a[0]+b[1] |a[1]+b[1] |a[2]+b[1] |a[3]+b[1] |a[4]+b[1]
b[2] |a[0]+b[2] |a[1]+b[2] |a[2]+b[2] |a[3]+b[2] |a[4]+b[2]
b[3] |a[0]+b[3] |a[1]+b[3] |a[2]+b[3] |a[3]+b[3] |a[4]+b[3]
b[4] |a[0]+b[4] |a[1]+b[4] |a[2]+b[4] |a[3]+b[4] |a[4]+b[4]
做$m-1$ 次两路归并。

区间合并
左端点排序。