http://acm.fzu.edu.cn/problem.php?pid=2236
【FZU 2236 第十四个目标 （线段树）】思路：每次找到当前第i个数之前有多少个比第i个数小的数，将前边的情况累加起来并且加上1
线段树查找，离散化
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define N 200000
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define MOD 1000000007
#define met(a, b) memset (a, b, sizeof(a))const double EPS = 1e-8;
struct node
{
int l, r, sum;
}tree[N*4];
int val[N], Hash[N];
void Build (int rt, int l, int r)
{
tree[rt].l = l, tree[rt].r = r;
tree[rt].sum = 0;
if (l == r) return;
int mid = (l+r)/2;
Build (rt<<1, l, mid);
Build (rt<<1|1, mid+1, r);
}void Insert (int rt, int x, int sum)
{
tree[rt].sum = (tree[rt].sum+sum) % MOD;
if (tree[rt].l == tree[rt].r) return;
int mid = (tree[rt].l+tree[rt].r)/2;
if (x<=mid) Insert (rt<<1, x, sum);
else Insert (rt<<1|1, x, sum);
}int Query (int rt, int l, int r)
{
if (l > r) return 0;
if (tree[rt].l == l && tree[rt].r == r)
return tree[rt].sum;
int mid = (tree[rt].l+tree[rt].r)/2;
if (r <= mid) return Query (rt<<1, l, r);
else if (l > mid) return Query (rt<<1|1, l, r);
else
{
int a = Query (rt<<1, l, mid);
int b = Query (rt<<1|1, mid+1, r);
return (a+b)%MOD;
}
}int main ()
{
int n;
while (scanf ("%d", &n) != EOF)
{
for (int i=0;
i 推荐阅读
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN
- 牛客 C. 子段乘积（线段树）
- 牛客挑战赛39 C 牛牛的等差数列（线段树）（*）
- 牛客 数据结构（区间修改+求区间元素平方和）
- 校门外的树 线段树版
- 树链剖分|牛客练习赛51 F-ABCBA（树链剖分，线段树，状态转移）
- 数论|bzoj 1938 - 类欧几里得+线段树
- 线段树|FZU - 2277(树链剖分或dfs序+线段树)
- 并查集|[CF938G] Shortest Path Queries
- 牛客网 练习赛25 B最长区间