111qqz的小窝

老年咸鱼冲锋!

codeforces 540 E. Infinite Inversions (分类思想+线段树求逆序对)

题目链接 题意:一个无穷数列,从1开始,初始第i个位置上为i,给出n个swap,每次交换两个位置的数。问交换n次以后得到的数列中,逆序对的数。

codeforces 515 E. Drazil and Park ( 线段树区间合并)

题目链接 题意:圆上,询问任意一段弧中,任意两点的距离+两点的权值和的最大值。 思路: 1.环先拆成串,复制1..n到后面,变成1..2n。 化简公

codeforces #351 D. Jeff and Removing Periods (线段树/树状数组判断位置成等差数列)

题目链接 题意:有n个数,每次可以删除掉数值相同并且所在位置成等差数列(只删2个数或者只删1个数应该也是可以的),删掉这些数以后可以将剩下的数

spoj DQUERY - D-query (询问区间中不同数的个数,线段树(离线) or 莫队算法(离线) or 主席树(在线))

题目链接 题意:给出n个数,然后m个询问,每个询问一个区间[l,r],问该区间中不同的数有多少个。 思路:离线处理+线段树的做法不多说了: /* *********************************************** Author

codeforces 338 E. Optimize! (线段树维护最小前缀和)

题目链接 题意:题意是由伪代码给出的。。手算模拟了一下(noip初赛即视感),题意大概是说,给出两个数组a和b,a数组长度为n,b数组长度为l

BZOJ 1756: Vijos1083 小白逛公园  (线段树维护单点修改区间查询最大子段和)

1756: Vijos1083 小白逛公园 Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1078 Solved: 353 [Submit][Status][Discuss] Description 小新经常陪小白去公园玩,也就是所谓的遛狗啦…在小新家附近有一条“公园路”,路的一边从南到北依次排着

hit oj 2687 Candy (线段树动态维护最大连续子段)

题目链接 题意:给出n个数,m个修改,每次修改后询问整个区间的最大连续子段。 思路:考虑一段区间,分成左右两个子区间,这段区间的最大子段有三种情

codeforces 501 D Misha and Permutations Summation (康托展开+康托逆展开+factorial_number_system+线段树×2)

题目链接 题意:给出两个排列,定义ord(p)为排列p的顺序(字典顺从小到大),定义perm(x)为顺序为x的排列,现在要求1 ≤ n ≤ 200 000 思路:

light oj 1080 Binary Simulation (线段树lazy标记,区间更新,单点查询)

题目链接 题意:给出一个长度为n的数列,每个位置是0或者1,给出q个操作,操作有两种类型,分别是将一段区间中反转,和询问当前某位置是0还是1 思

codeforces 356 A. Knight Tournament (线段树lazy标记,倒序处理)

思路:由于先前被打败的骑士直接就退场了。。。所以如果不做判断。。那么之后胜利的骑士会干扰之前的结果。。。 可以在pushdown的时候加判断。

codeforces 292 E. Copying Data (染色问题,线段树lazy标记模板题)

x题目链接 题意:给出两个数组,每个数组n个数,分别为a和b,给出m个操作,操作有两种类型,第一种是给出x,y,k,表示从a数组的x坐标开始复

codeforces 474 F. Ant colony (线段树求gcd+统计区间中某数出现的次数的经典做法)

题目链接 题意:给出n个数,m个查询,每组查询一个区间[l,r],问[l,r]中会被吃掉多少个(区间[l,r]中的数只有当其是其他所有数的因数

codeforces 61 E. Enemy is weak (离散化+线段树求逆序三元组)

题目链接 题意:给出n个数,求满足 i<j<k且a[i]>a[j]>a[k]的三元组有多少个。 思路:对于这种要求三个数满

codeforces 459 D. Pashmak and Parmida's problem (离散化+线段树求逆序对数)

题目链接 题意:定义_f_(_l_, _r_, _x_)为区间[l,r]中x出现的次数。现在要求calculate the number of pairs of indicies _i_, _j_ (1 ≤ _i_ < _j_ ≤ _n_) such that_f_(1, _i_, _a__i_)

codeforces 339 D. Xenia and Bit Operations(线段树)

题目链接 题意:给出n和m,初始给出1«n个数,先相邻的两个数进行或操作(a[1]^a[2],a[3]^a[4]…)

codeforces 19 D. Points (离散化+树套树(线段树+set))

题目链接 题意: 1.add x,y 将点(x,y)加进坐标系。 2.remove x,y 将点(x,y)移除. 3.find x,y 找到点(x,y)右上角的点(xp>x,yp>y)。如果有

poj 2828 Buy Tickets (线段树单点更新,逆序插入)

poj 2828 题目链接 题意:n个人,每个人有一个rp值(用来区分不同的人),还有一个pos[i],表示当第i个人来排队的时候插入到第pos[i]个人的

hdu 1754 I Hate It (线段树模板题,炒鸡详细注释版)

hdu 1754 题目链接 题意:单点更新,区间查询最大值。 思路:线段树。 一开始借鉴了clj的pointer写法。。wjmzbmr's code 直接MLE。。。看来

线段树学习笔记

嘛,终于下定决心搞定线段树了。 之前几次都是被lazy标记卡住,这次大概不会了吧2333 放一些学习资料,最后比较zkw线段树和普通线段树的区别

hdoj 2795 Billboard

http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意:一个尺寸为wh的方格。要按顺序放放n个尺寸为1wi的纸条。问每一个纸条回被放在哪里。如果有多个,放在最上面(编号小) 思路:把没横行能