P4054 [JSOI2009]计数问题 题目描述 一个n*m的方格,初始时每个格子有一个整数权值.接下来每次有2种操作: 改变一个格子的权值: 求一个子矩阵中某种特定权值出现的个数. 输入输出格式 输入格式: 第一行有两个数N,M. 接下来N行,每行M个数,第i+1行第j个数表示格子(i,j)的初始权值. 接下来输入一个整数Q. 之后Q行,每行描述一个操作. 操作1:"1 x y c"(不含双引号).表示将格子(x,y)的权值改成c(1<=x<=n,1<=y<

HDU 5862 Counting Intersections(离散化+树状数组) 题目链接http://acm.split.hdu.edu.cn/showproblem.php?pid=5862 Description Given some segments which are paralleled to the coordinate axis. You need to count the number of their intersection. The input data guarant

Luogu 2680 NOIP 2015 运输计划(树链剖分,LCA,树状数组,树的重心,二分,差分) Description L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球. 小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物 流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去.显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之

洛谷题目连接:洛谷树 题目背景 萌哒的Created equal小仓鼠种了一棵洛谷树! (题目背景是辣鸡小仓鼠乱写的QAQ). 题目描述 树是一个无环.联通的无向图,由n个点和n-1条边构成.树上两个点之间的路径被定义为他们之间的唯一一条简单路径--显然这是一条最短路径. 现在引入一个概念--子路径.假设树上两个点p1和pn之间的路径是P=<p1,p2,p3,-,pn>,那么它的子路径被定义为某一条路径P',满足P'=<pi,pi+1,pi+2,-,pj>,其中1<=i<

题目描述 排排坐,吃果果,生果甜嗦嗦,大家笑呵呵.你一个,我一个,大的分给你,小的留给我,吃完果果唱支歌,大家乐和和.红星幼儿园的小朋友们排起了长长地队伍,准备吃果果.不过因为小朋友们的身高有所区别,排成的队伍高低错乱,极不美观.设第i个小朋友的身高为hi,我们定义一个序列的杂乱程度为:满足i<j且hi>hj的(i,j)数量.幼儿园阿姨每次会选出两个小朋友,交换他们的位置,请你帮忙计算出每次交换后,序列的杂乱程度.为方便幼儿园阿姨统计,在未进行任何交换操作时,你也应该输出该序列的杂乱程度. 输

Description 前缀和(prefix sum)\(S_i=\sum_{k=1}^i a_i\). 前前缀和(preprefix sum) 则把\(S_i\)作为原序列再进行前缀和.记再次求得前缀和第i个是\(SS_i\) 给一个长度n的序列\(a_1, a_2, \cdots, a_n\)有两种操作: Modify i x:把\(a_i\)改成\(x\): Query i:查询\(SS_i\) Input 第一行给出两个整数N,M.分别表示序列长度和操作个数 接下来一行有N个数,即给定的

题目描述 给你一个N*N的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第K小数. 输入 第一行两个数N,Q,表示矩阵大小和询问组数:接下来N行N列一共N*N个数,表示这个矩阵:再接下来Q行每行5个数描述一个询问:x1,y1,x2,y2,k表示找到以(x1,y1)为左上角.以(x2,y2)为右下角的子矩形中的第K小数. 输出 对于每组询问输出第K小的数. 样例输入 2 2 2 1 3 4 1 2 1 2 1 1 1 2 2 3 样例输出 1 3 题解 整体二分+二维树状数组 题目答案具有很明显的

UVA1406 - A Sequence of Numbers(树状数组) 题目链接 题目大意: 给定N个数字.给两种操作:C x: 把这N个数字都加上x. Q x:查询这N个数里面有多少个数字和2^x取且大于0.最后把每一个查询的结果求和作为答案. 解题思路: 查询与2^x取且为1,那么就意味这那个符合要求的数的第x位要是1. 可是这里还有所有加上x的操作,能够用一个变量来记录所有C操作的x的和.有这个加数的话,第x位为1的可能能够通过低位进位得到,所以这里开16个树状数组,第i个树状数组存放

P2184 贪婪大陆  题目 其实很容易理解就是询问一段区间内有多少段不同的区间 然后再仔细思索一下会发现: 1.只要一个区间的开头在一个节点i的左边,那么这个区间包含在区间1~i中. 2.只要一个区间的尾部在一个节点j的左边,那么这个区间肯定不属于j之后的所有区间 这时候就不难想到用两个树状数组维护: 第一个:维护节点i之前有多少个区间的开头 第二个:维护节点j之前有多少个区间的结尾 不难证明拿sum[i]-sum[j]得到的就是i~j中间地雷的个数(手动模拟一波就一清二楚了) #includ

实验室外的攻防战 UOJ#180 [树状数组] 题目 时针指向午夜十二点,约定的日子--2月28日终于到来了.随着一声枪响,伏特跳蚤国王率领着他的跳蚤大军们包围了 \(picks\) 博士所在的实验室. 当然,\(picks\) 博士不会坐以待毙,他早就率领着他的猴子们在实验室外修筑了许多的坚固防御工事. 经过跳蚤侦察兵的勘察,跳蚤国王发现 \(picks\) 博士的防御工事有着 \(n\) 处薄弱点,于是他把他的跳蚤大军分成了 \(n\) 支小队,并打算让它们分别进攻每一个薄弱点.但是因为战场

洛谷题目传送门 YCB巨佬对此题有详细的讲解.%YCB%请点这里 思路分析 不能套用静态主席树的方法了.因为的\(N\)个线段树相互纠缠,一旦改了一个点,整个主席树统统都要改一遍...... 话说我真的快要忘了有一种数据结构,能支持单点修改,区间查询,更重要的是,常数优秀的它专门用来高效维护前缀和!!它就是-- !树状数组! 之前静态主席树要保存的每个线段树\([1,i]\),不也是一个庞大的前缀吗?于是,把树状数组套在线段树上,构成支持动态修改的主席树.每个树状数组的节点即为一个线段树的根节点

题目链接:https://www.luogu.org/problemnew/show/P3655 不一定对,仅供参考,不喜勿喷,不喜勿喷. 先copy洛谷P3368 [模板]树状数组 2 题解里面一位大佬Lyp10000对差分数组的解释: 来介绍一下差分 设数组a[]={,,,,},那么差分数组b[]={,,,-,} 也就是说b[i]=a[i]-a[i-];(a[]=;),那么a[i]=b[]+....+b[i];(这个很好证的). 假如区间[,]都加上2的话 a数组变为a[]={,,,,},b

洛谷题目传送门 一血祭 向dllxl致敬! 算是YNOI中比较清新的吧,毕竟代码只有1.25k. 首先我们对着题意模拟,寻找一些思路. 每次选了一个最大的数后,它和它周围两个数都要减一.这样无论如何,我们都选不到旁边那两个数,只有第一次选的那个数会对答案产生它的大小的贡献. 于是就可以写出一个\(O(nm\log n)\)的暴力用来对拍了 #include<bits/stdc++.h> #define LL long long #define R register int #define G

原文链接http://www.cnblogs.com/zhouzhendong/p/8672131.html 题目传送门 - BZOJ3262 题目传送门 - 洛谷P3810 题意 有$n$个元素,第$i$个元素有$a_i$.$b_i$.$c_i$三个属性,设$f(i)$表示满足$a_j\leq a_i$且$b_j\leq b_i$且$c_j\leq c_i$的$j$的数量.对于$d\in [0,n)$,求$f(i)=d$的数量. $n\leq 100000,max\{a_i,b_i,c_i|i

洛谷题目传送门 emm...题目名写了个平衡树,但是这道题的理论复杂度最优解应该还是树状数组套值域线段树吧. 就像dynamic ranking那样(蒟蒻的Sol,放一个link骗访问量233) 所有的值(包括初始a数组,操作1.3.4.5的k)全部先丢进去离散化 对于1操作查比它小的数,挑log棵线段树,找区间小于这个数的个数+1,这个还比较好像 操作2就是dynamic ranking,log棵线段树一起加减,像静态主席树求第k小一样跳,操作3 dynamic ranking里也有 操作4先

题目链接 洛谷P3759 题解 树状数组套主席树板题 #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<map> #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt) #define REP(i,n) for (int i = 1

传送门(uoj) 传送门(洛谷) 这里是题解以及我的卡常数历程 话说后面那几组数据莫不是lxl出的这么毒 首先不难发现这个东西把查询前缀和变成了查询后缀和,结果就是查了\([l-1,r-1]\)的区间和.因为模\(2\)意义下的加法就是异或,所以错误查询和正确查询相等就意味着\(a[l-1]\)和\(a[r]\)相等 我们不能简单的维护每个位置是什么值的概率,比方说一次修改了\([1,2]\),虽然这两个位置为\(1\)的概率都是\(\frac{1}{1}\),但它们的值绝对不相等 所以我们需要

题目: 洛谷4396 BZOJ3236(权限) 这题似乎BZOJ上数据强一些? 分析: 这题真的是--一言难尽 发现题面里没说权值的范围,怕出锅就写了离散化.后来经过面向数据编程(以及膜神犇代码)知道最大权值\(1e5\)(下文用\(M\)表示最大权值.注意如果没有这个限制,把所有数的权值和询问中提到的权值一起离散化后\(M\)也可以达到\(n+2m=2.1e6\)),如果没这个限制我很想知道正解应该怎么写--下面再细说 首先看到这种询问某个区间内在某个区域内值的数量的题,显然能想到把询问离线下

### 洛谷P4396  题目链接 ### 题目大意: 有 n 个整数组成的数组,m 次询问,每次询问中有四个参数 l ,r,a,b .问你在[l,r] 的区间内的所有数中,值属于[a,b] 的数的个数以及种类数. 分析: 1.由于可以离线操作,故采用莫队. 2.由于在莫队的基础上还涉及区间[a,b]的值的个数,故可以用前缀和的思想,求得出sum(b) - sum(a - 1)即可.由于与莫队使用是动态的,故需要用树状数组维护,因为可以 logn 动态插入. 3.对于求区间种类数,需要用第二个树

其实已经学了树状数组和线段树,然而懒得做题,所以至今没写多少博客 Description 现在请求你维护一个数列,要求提供以下两种操作: 1. 查询操作. 语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值. 限制:L不超过当前数列的长度.(L>=0) 2. 插入操作. 语法:A n 功能:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾. 限制:n是整数(可能为负数)并且在长整

[NOIP2013提高&洛谷P1966]火柴排队 Description 涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度. 现在将每盒中的火柴各自排成一列, 同一列火柴的高度互不相同, 两列火柴之间的距离定义为: ∑(ai-bi)^2 其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度. 每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小.请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小