iTom's blog

poj 2528 Mayor's posters离散化要注意一个细节有个数组不知道为什么要开那么大还有，update() 和 query() 的时候用左闭右开形式的区间错了好多次，后来换成闭区间的形式才过的

Meaning给出 n 个矩形，求它们并出来的图形的周长（内、外的边都算）

一个 m * m 的网格里有 n 个点，现要从任意一个角落开始引出一个矩形，使得矩形内的点数恰好是总点数一半，且面积要尽量小，求这个最小面积

给出 n 个矩形，求它们相交部分的总面积

平面上有若干个矩形，可能有重叠，问总的面积是多少（重叠部分只算一次）

给出若干个平面上的矩形，问总的面积（重叠部分算一次）

给一个整数序列 s，每个数都有个权值，从序列中找一个非降的子序列，使得该子序列的权值和最大，求这个最大的权值

一棵 n 个点的树，每给结点有个值。两种操作：树上指定路径上结点的值同时加上 k；讯问特定点的值

Problemacm.csu.edu.cn/csuoj/problemset/problem?pid=1811vjudge.net/contest/161962#problem/IReferenceblog.csdn.net/qwb492859377/article/details/52436186www.cnblogs.com/fightfordream/p/6801852....

区间第 k 大数，主席树模板

二维线段树的成段更新

二维线段数的单点更新、查询模板题

给一个 n * n 的矩阵 A，开始时所有值是 0。有两种操作：1. Q x y：询问 A[x][y] 的值是多少2. C x1 y1 x2 y2：将以 ( x1 , y1 ) 为左下角、( x2 , y2 ) 为右上角的子矩阵中的所有值都反转

给出一个平衡的括号序列，q 个询问，每次问交换 a 和 b 位置的括号后得到的序列是否仍是平衡括号序列。

n 个员工之间的上司下属关系成一棵树，每个员工有一个上司（老板除外）和零个或多个下属。有两种操作：C x：询问编号为 x 的员工当前的工作T x y：给编号为 x 的员工分配新工作 y当员工被分配新工作时，旧工作被覆盖；该员工和他所有的下属（包扩下属的下属）同时被分配这个新工作（一次改整棵子树）。

n个村庄连成一条线，有3种操作：D x：摧毁编号为 x 的村庄Q x：询问与编号为 x 的村庄相连的村庄的数量（包括 x 自身）R：修复最近一次被摧毁的那个村庄（恢复与相邻村庄的连接）

题意：给一列值，每次操作要么更新都使得区间 [ left , right ] 内的每一个值都变成原来的平方根（再向下取整）；要么询问区间 [ left , right ] 的值的总和。分析：这种更新不像以前见的成段更新，因为区间内每个值的变化都不一样。考虑到：1开方之后还是1，所以一个区间如果所有值都小于等于1（没说一定大于0…但按题意应该是把…）的时侯就不用再往下更新。题目说总和不超过 2^63，就算 2^64，最多开 7 次方就到 1（所以是不会太耗时的意思吧？）

线段树成段更新第一点，题中给出的边界是线段的两个端点，也就是说每个标号表示一个点而不是一个小线段。于是我采用标号表示它右边的一段，所以输入“x1 x2 c”，我处理成：update(x1, x2-1, c, ...)。第二点，连在一起的两段同色段要合并成一大段，但不能简单写个 pushup() 来完成，因为两个同色段可能分在两个结点所管的区间内，但又没有结点所管的区间那么长，所以会出现漏合并的情况。于是多开一个 col 数组，在 query 的时侯，把更新完的最后结果都放进这个数组中，然后再用一个循环

n 种物品，每种 ai元。q 个人，初始有 vi 元，按顺序买 [ li，ri ] 的物品，能买多少买多少，问最后每个人都剩多少钱