链接：P3374 【模板】树状数组 1 ------------------------------------------------------- 树状数组是个很有用的数据结构，当然，有许多时候我们也可以用线段树代替他。 不过线段树比树状数组难得多，所以应该是用树状数组代替线段树才对。   比如说看看这个：[洛谷日报第22期]可以代替…

a

a

  链接：P1631 在做这道题前，我们来考虑这样的一个问题   已知一个n*n的数表，保证在每一行上，有a[i][j]<a[i][j+1],我们怎样求出它的第k小的值？ 对于这个问题，我们   在做这道题前，我们来考虑这样的一个问题       已知一个n*n的数表，保证在每一行上…

  这道题还是很有趣的 大佬们都用了搜索，DP等做法，而本蒟蒻刚刚学了二维前缀和，所以就用了二维前缀和来做这道题 什么是二维前缀和？ （你一定知道什么是一维前缀和） 二维前缀和就是一维前缀和多了一维，它的计算公式是 s[i][j]=s[i-1][j]+v[i][j]+s[i][j-1]-s[i-1][j-1]; 为什么最后还要减？如果你画…

include<bits/stdc++.h>using namespace std;const int N = 3e5;int n,m;int a[N],p[N];inline void readl(int &x){ x=0; int s=1; char ch=getchar(); while(ch<'0'||ch>…

这可真是星球大战 链接： P1197 ----------------------------------------- 看一下这道题，如果我们正着做，每摧毁一个后就重新建图，判连通。这样肯定工程浩大且超时，我们就要换个方法了。 为什么不倒着做呢？我们先求出来最后剩下的数量，然后倒着恢复一个又一个的星球，并且重新判断这个星球的连通状况。 欸，这样好…

include<iostream>#include<cstdio>#include<algorithm> using namespace std;const long INF = 1e9;int a[10000];int b[10000];long long a1[200001];int n; int deall…

题目链接：Miku 这道题看第一眼可能想到暴搜，从每个点开始向右找到第一个大于它的点并且计算距离 然而绝对会TLE 这时候我们就要找到一个数据结构了——单调栈。 单调栈，顾名思义，就是和单调队列一样的东西。只不过一个是栈，一个 是队列 （不知道单调队列是什么：这） 所谓单调，就是里面的元素都是按照某一关键字递增或递减。那么，…

加权并查集是些什么东西啊 P1196 这道题分为两部分考虑，首先考虑两个点是否在一个队列上，这个简单，用并查集就可以了，然而，我们还要考虑的一点是计算两个点的距离，这就怎么处理呢。 嗯，很容易（不）决定用前缀和，我们就会定义一个数组front，其中front[i]表示以i结尾前面的飞船数。这样我们就解决了计算，但是我们怎么维护front呢？ &nb…