补很久以前的坑 图片来自lxl课件 显然，将每栋楼房都求一个斜率，然后发现一个楼房能被看到可以等价于它的斜率比之前的任何一个都大。 于是我们要求∑i=1n[a[j]≤a[i] for j∈[1,i−1]]\sum _{i=1}^n [a[j] \le a[i] \ for \ j \in [1,i-1]]∑i=1n​[a[j]≤a[i] for j∈[1,i−1]]。 这个怎么求？ 考虑...

传送门 本题暴力： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include <bits/stdc++.h>#define MAXN 200005using nam...

BZOJ GDOI 对于每种颜色开一棵线段树，比如说对于颜色序列1 2 2 3 3 2\text {1 2 2 3 3 2}1 2 2 3 3 2，它的线段树开出来是这样的： 因为两种颜色搞在一起后，没有任何操作能把他们分开，不妨把替换视为合并。 比如把333替换成222，就是把333合并到222。 考虑如何pushup\rm pushuppushup，只要维护区间左右端点值(0/1)(...

传送门 先考虑一下暴力怎么打，对于每个时间，我们开一个vectorvectorvector，对于每一个任务，我们在[Si,Ei][S_i,E_i][Si​,Ei​]的vectorvectorvector里面都pushbackpushbackpushback一遍PiP_iPi​即可。 但是这样的暴力是愚蠢的暴力，考虑优化，我们在SiS_iSi​和Ei+1E_i+1Ei​+1的位置分别打上加入和...

传送门 一开始看到这道题，非常懵逼，不知道怎么做。 然后发现子弹是按照顺序发射的，于是转化一下题目条件，木板[Li,Ri][L_i,R_i][Li​,Ri​]会在接触到第SiS_iSi​个子弹时破掉，于是就转换成求[Li,Ri][L_i,R_i][Li​,Ri​]第SiS_iSi​大的子弹编号是多少。 这就是主席树模板嘛！ p.s.如果你懒（像我一样），不想把操作离线下来搞，就可以搞一下线段...

传送门 首先，看到区间修改，区间查询就要想到线段树。 把链上面的操作转化到点上面的的操作，我们像这样编号，点编号为1...n1...n1...n，边编号为1...n−11...n-11...n−1 于是修改和查询都对应到了边[l,r−1][l,r-1][l,r−1] 考虑如何算期望值，下面的分母很简单，就是Cr−l+12C_{r-l+1}^2Cr−l+12​，从r−l+1r-l+1r−l...

传送门 这道题思路还是比较巧妙的，考虑如何判断矛盾。 首先，发现题目中说 每个位置上的数都不同的序列a[1…n] 所以任意两个不相交的区间中，最小值一定是不同的（性质111），因为如果最小值相同，那么最小值对应到的那个数是相同的，说明两段区间都包含那个数，即两段区间相交。 再继续考虑，我们考虑二分答案，现在二分到一个位置pospospos，我们首先把位置≤pos\le pos≤pos的操...

传送门 我首先是这么想的，记录每个元素前一次出现的位置preprepre（判断是否重复），再维护一个最大值和最小值 后面发现这题原来还带修改，就放弃了这种想法。 考虑一个正确率较高的做法，维护区间每个数的平方和sumsumsum，最大值maxmaxmax和最小值minminmin，若查询区间长度不等于max−min+1max-min+1max−min+1，那么肯定不行，再算一下∑i=minm...

传送门 树链剖分裸题 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979...

传送门 考虑把所有线段按照长度排序，在排好序的序列上面跑尺取法，设尺取法维护的区间为[pl,pr][pl,pr][pl,pr]，一直移动右端点prprpr，直到现在有一个点在区间[pl,pr][pl,pr][pl,pr]代表的线段上面出现>=m>=m>=m次，停止移动右端点，开始移动左端点，直到没有点在区间[pl,pr][pl,pr][pl,pr]代表的线段上面出现>...