二维树状数组

BIT是最容易扩展到高维的数据结构了，对于一维(单点修改+区间查询)，我们是这样搞得…… #define lowbit(x) ((x)&(-(x))) void update(int pos,int val) { for(int i=pos;i<=n;i+=lowbit(i)) sum[i]+=val; } int que

2017-09-14

OI&ACM

Data Structure/数据结构 tree/树 BIT

进程表

2017年9月11日非考试 ID 题目状态思路注意 1 【bzoj2243】[SDOI2011]染色 TLE&WA/AC 树链剖分，线段树维护相同连续段数链合并时减去重复时是一条重链左端点颜色与另一条重链左端点颜色判断是否相等，而不是左与右，右与左考试 ID 题目状态思路注意 2 【09-11】卫星连接 100/100(AC) 将点权变为

2017-09-10

OI&ACM

记录

树链剖分模板

NOIP快来了，复习一下。题目描述如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：操作1：格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z操作2：格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和操作3：格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z操作4：格式： 4 x 表示求以x为根节

2017-09-08

OI&ACM

Data Structure/数据结构 Graph/图论树链剖分

[NOI 2004]郁闷的出纳员(bzoj 1503)

题目描述OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感，尤其是集体扣除工资的

2017-09-08

OI&ACM

Data Structure/数据结构 Treap tree/树

[hdu 3625]Posters(线段树 + 扫描线)

题目大意给定一些矩形，矩形中有矩形小孔，求矩形面积并。矩形个数$ \leq 5 \times 10^4$,$0 \leq$坐标$\leq 5 \times 10^4$传送门思路只需稍微转化的矩形面积并，把一个矩形拆成4个就行了，若小孔在边缘，拆后面积为0的也对答案无贡献，不用特殊讨论，而坐标为整数，范围也不大，不用离散化。将矩形拆为上下两条线段，上线段权值为1，下线段权值为-1，并按y轴坐标从

2017-09-05

OI&ACM

Data Structure/数据结构 tree/树线段树 scan-line

树状数组BIT的变幻

根据我们多年的经验，BIT是个常数小，维护区间的好东西。但似乎只能维护单点修改+区间查询(？？若真是这样，那我写这篇博文有什么用?->所有东西必有其存在意义)下面先给出最基本的BIT Code: #define lowbit(x) ((x)&(-(x))) void update(ll *a,int p,int val) { for(int i=p;i<

2017-09-03

OI&ACM

Data Structure/数据结构 tree/树 BIT 差分

[poj 2299]Ultra-QuickSort(离散化+逆序对)

题目大意给定若干个未排序的序列，利用冒泡排序原理(交换两个相邻序列元素)，求将它们各自变成升序的最小操作数，对于每一个序列输出一个答案。思路:其实还是求逆序对个数,但数的范围比较大( $1 \leq x \leq 9999999999$ ),而个数只有$5 \times 10^5$,此时便需要离散化。离散化STLconst int maxn=6e5+10; int a[maxn],b

2017-09-03

OI&ACM

Data Structure/数据结构 tree/树 BIT zkw 线段树离散化

[hdu 1394]Minimum Inversion Number(求逆序对)

题目大意求循环移动大小为n的数组后得到n个数组中的最小逆序对数(数组中数小于n)传送门a1, a2, ..., an-1, an (where m = 0 - the initial seqence) a2, a3, ..., an, a1 (where m = 1) a3, a4, ..., an, a1, a2 (where m = 2) ... an, a1,

2017-09-02

OI&ACM

Data Structure/数据结构 tree/树 BIT zkw 线段树

左偏树

暂时先来发代码 hdu1512 Monkey King //spaceskynet Leftist-Tree 2017-08-30 #include<iostream> #include<cstdio> using namespace std; const int maxn=1e5+10; struct node { int l,r

2017-08-31

OI&ACM

Data Structure/数据结构 tree/树左偏树

SYZOJ中文安装指南

Made By:SpaceskynetThanks to other developers. 测试系统 Ubuntu-17.04 PS(全局变量): [syzoj2 path] = 您git的syzoj的路径；[syzoj-judge path] = 您git的syzoj-judge的路径系统要求 1.node >=6.0.0 (node.js)2.npm3.p7zip-all &

2017-08-22

教程

指南 OJ