区间最值查询

RMQ 算法 RMQ 算法全称为（Range Minimum/Maximum Query），即区间最值查询，解决这种问题有两种比较高效的方法：分别为ST 算法以及线段树。它们两者都要进行一定的预处理。

【ST 算法】

预处理的核心思想是动态规划，通过把每一个点开始的一段区间不断一分为二，直至最后一段的长度为1，然后再一步一步返回回去。代码：

int Log( int N) {

}

void Table() {

for( int i=1; i

int n= Log(N);

for( int j=1; j

for( int i=1; i

if( i +(1

F[i][j]=max( F[i][j-1], F[i+(1

}

若输入：3 2 4 5 6 8 1 2 9 7

若序列生成ST 表如下：

上述代码是求区间最大值的算法，求最小值只需要稍作修改即可。但要注意，为了节省空间，我们按以下规律存储：F[i][j]表示的既是从return log((double)(N))/log(2.0);

第i 个点开始，到第(i+(1

F[i][j]=Max( F[i][j-1], F[i+(1

int RMQ( int nStart, int nEnd) {

int nLog =Log(nEnd-nStart+1);

return max( F[nStart][nLog], F[nEnd-(1

该算法的时间复杂度为O （NlogN ）

【线段树】（建造线段树）

和胜者树类似，线段树的空间需求也是4*N。

用递归构建胜者树：

void build(int node, int begin, int end) {

if (begin==end) segTree[node] =array[begin];

else {

build(2*node, begin, (begin+end)/2);

build(2*node+1, (begin+end)/2+1, end);

segTree[node]=max(segTree[2 *node], segTree[2 *node+1]);

}

}

查询与RMQ 原理相似，程序如下：

long long query( int x, int l, int r)

{

if( tree[x].l >=l && tree[x].r

if( tree[x].l > r || tree[x].r

return query( x*2, l, r)+query( x*2+1, l, r);

}

1247逆序对

[题目描述]

给定一个数组A ，它包含N 个整数，分别是A[1],A[2],...A[N]。如果存在下标i 和j ，使得 i

那么A 数组总共有多少对不同的“逆序对”？

范围

第一行为n(1≤n ≤100000) 。

接下来是n 行，每行一个长整型范围内的整数。

分析

此题需要用到离散化、数组计数，需要用线段树进行维护每个区间对应数值出现的数目。不断加入数，然后在线段树中快速查询每一段的和，加起来即可。

下面贴上代码：

#include

#include

#include

#include

#include

using namespace std;

const int ML=100021;

struct node

{

int l,r;

long long sum;

}tree[4*ML];

struct lsh {

int num, p;

}a[ML];

bool _sort(lsh x, lsh y) {

}

int n, m;

long long pm1[ML],pm2[ML];

void buildTree(int x,int l,int r)

{

tree[x].l=l, tree[x].r=r;

if( l==r) { tree[x].sum=0; return ; }

buildTree( x*2 , l , (l+r)/2);

buildTree( x*2+1, 1+((l+r)/2), r );

tree[x].sum=tree[x*2].sum+ tree[x*2+1].sum;

}

void update(int x,int s,int e)

{

update( x*2 , s, e);

update( x*2+1, s, e); if( tree[x].l==s&&tree[x].r==s) { } tree[x].sum+=e; return ; return x.nums || tree[x].r

}

long long query( int x, int l, int r)

{

if( tree[x].l >=l && tree[x].r

if( tree[x].l > r || tree[x].r

return query( x*2, l, r)+query( x*2+1, l, r);

}

long long ans=0;

int main()

{

freopen("1247.in","r",stdin); freopen("1247.out","w",stdout); tree[x].sum= tree[x*2].sum +tree[x*2+1].sum;

scanf("%d", &n);

for( int i=1; i

scanf("%d", &a[i].num); a[i].p=i;

}

buildTree(1,1, n);

sort( a+1, a+n+1, _sort); 离散化

int p=1;

pm1[1] = 1;

for( int i=2; i

}

for ( int i=1; i

} ans+=query(1, pm2[i]+1, 100000); update(1, pm2[i], 1); for( int i=1; i

}

printf("%lld", ans);

return 0;

}

1669碉堡

题目描述

中国长城有N 个碉堡，把长城看成一条数轴，每个碉堡看成数轴上的一个点，第i 个碉堡的坐标是X[i]。每个碉堡都有一个坚固度，第i 个碉堡的坚固度是S[i]。长城是用来抵抗外敌的，所以碉堡之间要联系。任意两个碉堡之间都要联系一次，因此N 个碉堡之间总共会有N ×(N-1)/2次联系。两个碉堡联系一次是需要代价的，比如第i 个碉堡与第j 个碉堡联系一次的代价cost[i][j] = abs(X[i]-X[j]) × max(S[i],S[j])，其中abs 是求绝对值。你的任务是输出N ×(N-1)/2次联系的总代价。

分析

此题跟逆序对十分相似，同样需要用线段树进行数组计数，不断修改线段树，一个一个加入数组，动态维护线段树，然后用logN 查询比a 小的有多少个，比a 大的有多少个。同时用到了乘法分配律来简化时间复杂度。

下面贴上代码：

#include

#include

#include

#include

const int INF=21000000;

using namespace std;

struct zmk {

int l, r; long long sum, s;

}tree[80010];

struct node {

int s,w;

}a[200010];

bool _sort(node x, node y) {

}

void build (int x, int l, int r) {

}

void update(int x,int u,int e) {

} if(tree[x].l==u&&tree[x].r==u) { } if(tree[x].l>u||tree[x].r

long long query1(int x, int l ,int r) {

}

long long query2(int x, int l ,int r) {

}

int main() {

freopen("1669.in", "r", stdin); freopen("1669.out", "w", stdout); int n, _max=-INF; scanf("%d", &n); for( int i=1; i=l&&tree[x].rr||tree[x].r=l&&tree[x].rr||tree[x].r

for( int i=1; i

long long cc=query2(1,a[i].w+1,20000)-a[i].w*query1(1, a[i].w+1, 20000 );

}

在这里强调一下：开数组数据范围要注意，避免溢出等情况。

1670围棋

题目描述

风靡一时的Alpha Go人工智能战胜了人类最顶级的围棋冠军，在业界引起了轰动。然而这与本题关系不大（哈哈），把围棋的棋盘看成是一个平面二维坐标系，把棋子抽象成平面二维坐标系里的一个点，总共有N 个棋子，第i 个棋子的坐标是（X[i],Y[i]）。棋子是分“级别的”， 第i 个棋子和第j 个棋子的关系有如下3种：

1、 棋子i 的级别比棋子j 的级别高，当且仅当： X[i] >= X[j]且Y[i] >= Y[j]，则棋子i 在棋子j 的右上方区域。

2、 棋子i 的级别比棋子j 的级别低，当且仅当： X[i]

3、 如果都不满足如上两个条件，则棋子i 和棋子j 不具备可比性。 对于第i 个棋子来说，它的级别F[i]就等于级别比它低的棋子的数量。 分析

此题跟逆序对十分相似，同样需要用线段树进行数组计数，不断修改线段树，一个一个加入数组，动态维护线段树，然后用logN 查询比a 小的有多少个，比a 大的有多少个。同时用到了乘法分配律来简化时间复杂度。 } printf("%lld", ans); ans+=(bb+cc)*a[i].s; update(1, a[i].w, 1);

其实这题简直就是水了点，对比逆序对，此题不用离散化，只需要我们将逆序对中的所有下标替换为此题的X 坐标。

下面堵上代码：

#include

#include

#include

#include

const int INF=21000000;

using namespace std;

struct zmk {

struct node {

int s, w, id;

}a[100010];

bool _sort(node x, node y) {

}

int b[100010];

void build (int x, int l, int r) {

}

void update(int x,int u,int e) {

if(tree[x].l==u&&tree[x].r==u) { tree[x].sum+=e; tree[x].l=l, tree[x].r=r; if(l==r) return ; build(x*2, l, (l+r)/2); build(x*2+1, (l+r)/2+1, r); return (x.s

} } if(tree[x].l>u||tree[x].r

long long query(int x, int l ,int r) {

}

int main() {

freopen("1670.in", "r", stdin); freopen("1670.out", "w", stdout); int n, _max=-INF; scanf("%d", &n); for( int i=1; i=l&&tree[x].rr||tree[x].r

}

} update(1, a[i].w, 1); for(int i=1; i

#include

#include

#include

#include

#include

using namespace std;

const int INF=2100083647;

struct node

{

int l, r;

long long max;

}tree[400010];

int n;

long long ans;

long long a[100010];

void buildTree(int x,int l,int r)

{

tree[x].l=l, tree[x].r=r;

if( l==r) { tree[x].max=a[l]; return ; }

buildTree( x*2 , l , (l+r)/2);

buildTree( x*2+1, 1+((l+r)/2), r );

tree[x].max=max(tree[x*2].max,tree[x*2+1].max) ;

}

long long query( int x, int l, int r) {

if( tree[x].l >=l && tree[x].r

if( tree[x].l > r || tree[x].r

}

int erfen(int x) {

}

int main() {

freopen("1667.in","r",stdin); freopen("1667.out","w",stdout); int l=0, r=n+1; while(l+1=a[x]) r=mid; else l=mid;

scanf("%d", &n);

for(int i=1; i

buildTree( 1, 1, n);

for( int i=1; i

ans+=erfen(i)-i;

}

printf("%lld", ans);

return 0; }

1665圆盘

题目描述

桌面上有N 个转盘，从左到右排放，编号从1到N 。每个转盘只能显示0至9中的一个数字。每个转盘有一个小开关，按转盘上的开关，转盘的数字就会自动加1，（如果转盘的数字是9，那么按开关时，转盘的数字就会变成0 ）。

Luka 现在玩这个游戏，他有两张白纸。

Luka 重复以下的步骤m 次（注意：下面的3个步骤要次序执行）：

（1）选两个整数A 、 B (1 ≤ A ≤ B ≤ N) 并且把它们写到第一张白纸上。

（2）把编号在区间[A，B]内（包括A 、B ）的所有转盘显示的数字逐一的加起来，把结果写到第二张白纸上。

（3）对编号在区间[A，B]内（包括A 、B ）的转盘，都按一次开关。 做完M 次这样的操作后，请你输出第二张白纸的数据。

分析

这题还是十分水的，动态维护十颗线段树，第一次做没经验…… 下面堵上代码：

#include

#include

#include

#include

#include

using namespace std;

struct node {

int l, r, add; long long sum; int n[10];

}tree[2000010];

int N, M;

char a[2500010];

void build( int x, int l, int r) {

tree[x].l=l, tree[x].r=r;

if( l==r) { tree[x].sum=a[l]-'0'; tree[x].n[a[l]-'0']++; return ; }

build( x*2 , l ,(l+r)/2);

build( x*2+1,1+((l+r)/2), r );

tree[x].sum= tree[x*2].sum+ tree[x*2+1].sum;

for( int i=0; i

}

long long _dat( int x) {

long long Sum=0;

int t[12];

for( int i=0; i

for( int i=0; i

return Sum;

}

void pushdown(int x) {

tree[x].sum=_dat(x);

tree[ x*2 ].add+=tree[x].add;

tree[x*2+1].add+=tree[x].add;

//tree[ x*2 ].sum=_dat(x*2);

//tree[x*2+1].sum=_dat(x*2+1);

tree[x].add=0;

}

void update(int x,int l,int r,int k)

{

if( tree[x].l>=l && tree[x].r

tree[x].add+=k;

}

long long query( int x, int l, int r) {

}

int main() {

freopen("1665.in","r",stdin); freopen("1665.out","w",stdout); scanf("%d %d", &N, &M); scanf("\n"); for( int i=1; i r || tree[x].r =l && tree[x].r r || tree[x].r

}

}*/ } scanf("%d %d", &aa, &bb); for( int j=aa; j= 10) a[j]='0'; return 0; build(1, 1, N); } return 0; int aa, bb; for( int i=1; i

1667 发型

题意：有n 头奶牛，从左往右排，每头奶牛都有一个高度，最左边的奶牛往右看，只能看到比它矮的奶牛。求最左边的奶牛所能看到的奶牛数量。

思路：这题从题目可以看出数据具有单调性：往右看右边一旦出现第一头奶牛比它高，无论后面的奶牛高度是多少，肯定也看不到那些奶牛。根据它的单调性及数据范围，我们可以想到二分的方法。二分一头奶牛的位置，如果从最左边的奶牛到这头奶牛的区间内，如果最高奶牛的高度小于最左边奶牛的高度，就证明还可以看到更多的奶牛，

就把区间缩小到mid-R ，反之则缩小到L-mid 。求区间内的最大值，我们很自然地可以想到线段树，做一遍线段树，判断一下，修改区间就解决这题了。

时间复杂度O(n log n log n)

参考程序：

#include

#include

#include

#include

#include

using namespace std;

const int INF=2100083647;

struct node

{

int l, r;

long long max;

}tree[400010];

int n;

long long ans;

long long a[100010];

void buildTree(int x,int l,int r)

{

tree[x].l=l, tree[x].r=r;

if( l==r) { tree[x].max=a[l]; return ; }

buildTree( x*2 , l , (l+r)/2);

buildTree( x*2+1, 1+((l+r)/2), r );

tree[x].max=max(tree[x*2].max,tree[x*2+1].max) ;

}

long long query( int x, int l, int r) {

if( tree[x].l >=l && tree[x].r r || tree[x].r

}

int erfen(int x) {

}

int main() {

freopen("1667.in","r",stdin); freopen("1667.out","w",stdout); int l=0, r=n+1; while(l+1=a[x]) r=mid; else l=mid;

scanf("%d", &n);

for(int i=1; i

buildTree( 1, 1, n);

for( int i=1; i

ans+=erfen(i)-i;

}

printf("%lld", ans);

return 0;

}

1668. 垃圾桶

本题采用的是动态规划+线段树求最小值的算法，先将每个区间按开始点排序，再使用动态规划。使用f[i]表示清洁前i 个垃圾桶所需

最小费用maps[i]和mapt[i]表示以i 结尾的清洁工清洁的区间。可以推出状态转移方程：f[i]=min (每个在maps[i]和mapt[i]之间结尾的区间+所需费用，f[i]).

下面贴上部分代码：

int main()

{

freopen ("1668.in","r",stdin);

freopen ("1668.out","w",stdout);

long long m,l,r;

cin>>m>>l>>r;

r=r-l+1;

for (int i=1; i

{

cin>>stw[i].s>>stw[i].t>>stw[i].w;

stw[i].s-=l-1;

stw[i].t-=l-1;

}

sort (stw+1,stw+m+1,xx);

l=1;

build (1,0,r);

for (int i=0; i

{

maps[i]=m+1;

mapt[i]=0;

}

for (int i=m; i; i--) maps[stw[i].t]=i;

for (int i=1; i

update (1,0,f[0]=0);

for (int i=1; i

{ //头 //尾

}

} f[i]=INF; for (int j=maps[i]; j

1666 售票系统

题意：某次列车途经C 个城市，城市编号依次为1到C ，列车上共有S 个座位，每一个售票申请包含三个参数， O 为起点，D 为目的地站，N 为车票张数。售票系统对该售票申请受理或不受理的决定，只有在从O 到D 的区段内列车上都有N 个或N 个以上的空座位时该售票申请才被受理。请你写个程序，实现这个自动售票系统。

思路：求一个区间内的值的问题我们会想到线段树，因为它必须保证区段内都有那么多座位，所以我们要考虑最坏情况，即在线段树内记录该区间的最少座位数，每一次都要进行修改和维护

注意：这里有一个坑，就是终点站不能算入区间内，就是相当于把相邻两个车站之间连一条边，把边看成线段树。简单来说就是在输入时，加一句D - -。

参考程序：

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

long long s[60010],oo=2147483647;

int C,S,R,O,D,N;

struct data

{

long long sum,add;

}tree[4*60010];

void build(long long now, long long L, long long R)

{

if (L==R) {tree[now].sum=s[L];}

else

{

build(now*2,L,(L+R)/2);

build(now*2+1,(L+R)/2+1,R);

tree[now].sum=min(tree[now*2].sum,tree[now*2+1].sum);

}

}

void down(long long root, long long L, long long R)

{

int LS=root*2,RS=root*2+1,mid=(L+R)/2;

tree[LS].add+=tree[root].add;

tree[RS].add+=tree[root].add;

tree[LS].sum+=tree[root].add;

tree[RS].sum+=tree[root].add;

tree[root].add=0;

}

void update(long long now, long long L, long long R, int x, int y, int v)

{

if (x>R || y

if (x=R)

{

tree[now].add+=v; tree[now].sum+=v; return;

}

down(now,L,R);

update(now*2,L,(L+R)/2,x,y,v);

update(now*2+1,(L+R)/2+1,R,x,y,v);

tree[now].sum=min(tree[now*2].sum,tree[now*2+1].sum);

}

long long query(long long now, long long L, long long R, int x, int y) {

if (x>R || y

if (x=R) return tree[now].sum;

down(now,L,R);

return

min(query(now*2,L,(L+R)/2,x,y),query(now*2+1,(L+R)/2+1,R,x,y));

}

int main()

{

freopen("1666.in","r",stdin);

freopen("1666.out","w",stdout);

cin>>C>>S>>R;

for (int i=1; i

build(1,1,C);

for (int i=1; i

{

scanf("%d%d%d",&O,&D,&N); D--;

if (query(1,1,C,O,D)

else

{

update(1,1,C,O,D,-N);

cout

}

}

return 0;

}

RMQ 算法 RMQ 算法全称为（Range Minimum/Maximum Query），即区间最值查询，解决这种问题有两种比较高效的方法：分别为ST 算法以及线段树。它们两者都要进行一定的预处理。

【ST 算法】

预处理的核心思想是动态规划，通过把每一个点开始的一段区间不断一分为二，直至最后一段的长度为1，然后再一步一步返回回去。代码：

int Log( int N) {

}

void Table() {

for( int i=1; i

int n= Log(N);

for( int j=1; j

for( int i=1; i

if( i +(1

F[i][j]=max( F[i][j-1], F[i+(1

}

若输入：3 2 4 5 6 8 1 2 9 7

若序列生成ST 表如下：

上述代码是求区间最大值的算法，求最小值只需要稍作修改即可。但要注意，为了节省空间，我们按以下规律存储：F[i][j]表示的既是从return log((double)(N))/log(2.0);

第i 个点开始，到第(i+(1

F[i][j]=Max( F[i][j-1], F[i+(1

int RMQ( int nStart, int nEnd) {

int nLog =Log(nEnd-nStart+1);

return max( F[nStart][nLog], F[nEnd-(1

该算法的时间复杂度为O （NlogN ）

【线段树】（建造线段树）

和胜者树类似，线段树的空间需求也是4*N。

用递归构建胜者树：

void build(int node, int begin, int end) {

if (begin==end) segTree[node] =array[begin];

else {

build(2*node, begin, (begin+end)/2);

build(2*node+1, (begin+end)/2+1, end);

segTree[node]=max(segTree[2 *node], segTree[2 *node+1]);

}

}

查询与RMQ 原理相似，程序如下：

long long query( int x, int l, int r)

{

if( tree[x].l >=l && tree[x].r

if( tree[x].l > r || tree[x].r

return query( x*2, l, r)+query( x*2+1, l, r);

}

1247逆序对

[题目描述]

给定一个数组A ，它包含N 个整数，分别是A[1],A[2],...A[N]。如果存在下标i 和j ，使得 i

那么A 数组总共有多少对不同的“逆序对”？

范围

第一行为n(1≤n ≤100000) 。

接下来是n 行，每行一个长整型范围内的整数。

分析

此题需要用到离散化、数组计数，需要用线段树进行维护每个区间对应数值出现的数目。不断加入数，然后在线段树中快速查询每一段的和，加起来即可。

下面贴上代码：

#include

#include

#include

#include

#include

using namespace std;

const int ML=100021;

struct node

{

int l,r;

long long sum;

}tree[4*ML];

struct lsh {

int num, p;

}a[ML];

bool _sort(lsh x, lsh y) {

}

int n, m;

long long pm1[ML],pm2[ML];

void buildTree(int x,int l,int r)

{

tree[x].l=l, tree[x].r=r;

if( l==r) { tree[x].sum=0; return ; }

buildTree( x*2 , l , (l+r)/2);

buildTree( x*2+1, 1+((l+r)/2), r );

tree[x].sum=tree[x*2].sum+ tree[x*2+1].sum;

}

void update(int x,int s,int e)

{

update( x*2 , s, e);

update( x*2+1, s, e); if( tree[x].l==s&&tree[x].r==s) { } tree[x].sum+=e; return ; return x.nums || tree[x].r

}

long long query( int x, int l, int r)

{

if( tree[x].l >=l && tree[x].r

if( tree[x].l > r || tree[x].r

return query( x*2, l, r)+query( x*2+1, l, r);

}

long long ans=0;

int main()

{

freopen("1247.in","r",stdin); freopen("1247.out","w",stdout); tree[x].sum= tree[x*2].sum +tree[x*2+1].sum;

scanf("%d", &n);

for( int i=1; i

scanf("%d", &a[i].num); a[i].p=i;

}

buildTree(1,1, n);

sort( a+1, a+n+1, _sort); 离散化

int p=1;

pm1[1] = 1;

for( int i=2; i

}

for ( int i=1; i

} ans+=query(1, pm2[i]+1, 100000); update(1, pm2[i], 1); for( int i=1; i

}

printf("%lld", ans);

return 0;

}

1669碉堡

题目描述

中国长城有N 个碉堡，把长城看成一条数轴，每个碉堡看成数轴上的一个点，第i 个碉堡的坐标是X[i]。每个碉堡都有一个坚固度，第i 个碉堡的坚固度是S[i]。长城是用来抵抗外敌的，所以碉堡之间要联系。任意两个碉堡之间都要联系一次，因此N 个碉堡之间总共会有N ×(N-1)/2次联系。两个碉堡联系一次是需要代价的，比如第i 个碉堡与第j 个碉堡联系一次的代价cost[i][j] = abs(X[i]-X[j]) × max(S[i],S[j])，其中abs 是求绝对值。你的任务是输出N ×(N-1)/2次联系的总代价。

分析

此题跟逆序对十分相似，同样需要用线段树进行数组计数，不断修改线段树，一个一个加入数组，动态维护线段树，然后用logN 查询比a 小的有多少个，比a 大的有多少个。同时用到了乘法分配律来简化时间复杂度。

下面贴上代码：

#include

#include

#include

#include

const int INF=21000000;

using namespace std;

struct zmk {

int l, r; long long sum, s;

}tree[80010];

struct node {

int s,w;

}a[200010];

bool _sort(node x, node y) {

}

void build (int x, int l, int r) {

}

void update(int x,int u,int e) {

} if(tree[x].l==u&&tree[x].r==u) { } if(tree[x].l>u||tree[x].r

long long query1(int x, int l ,int r) {

}

long long query2(int x, int l ,int r) {

}

int main() {

freopen("1669.in", "r", stdin); freopen("1669.out", "w", stdout); int n, _max=-INF; scanf("%d", &n); for( int i=1; i=l&&tree[x].rr||tree[x].r=l&&tree[x].rr||tree[x].r

for( int i=1; i

long long cc=query2(1,a[i].w+1,20000)-a[i].w*query1(1, a[i].w+1, 20000 );

}

在这里强调一下：开数组数据范围要注意，避免溢出等情况。

1670围棋

题目描述

风靡一时的Alpha Go人工智能战胜了人类最顶级的围棋冠军，在业界引起了轰动。然而这与本题关系不大（哈哈），把围棋的棋盘看成是一个平面二维坐标系，把棋子抽象成平面二维坐标系里的一个点，总共有N 个棋子，第i 个棋子的坐标是（X[i],Y[i]）。棋子是分“级别的”， 第i 个棋子和第j 个棋子的关系有如下3种：

1、 棋子i 的级别比棋子j 的级别高，当且仅当： X[i] >= X[j]且Y[i] >= Y[j]，则棋子i 在棋子j 的右上方区域。

2、 棋子i 的级别比棋子j 的级别低，当且仅当： X[i]

3、 如果都不满足如上两个条件，则棋子i 和棋子j 不具备可比性。 对于第i 个棋子来说，它的级别F[i]就等于级别比它低的棋子的数量。 分析

此题跟逆序对十分相似，同样需要用线段树进行数组计数，不断修改线段树，一个一个加入数组，动态维护线段树，然后用logN 查询比a 小的有多少个，比a 大的有多少个。同时用到了乘法分配律来简化时间复杂度。 } printf("%lld", ans); ans+=(bb+cc)*a[i].s; update(1, a[i].w, 1);

其实这题简直就是水了点，对比逆序对，此题不用离散化，只需要我们将逆序对中的所有下标替换为此题的X 坐标。

下面堵上代码：

#include

#include

#include

#include

const int INF=21000000;

using namespace std;

struct zmk {

struct node {

int s, w, id;

}a[100010];

bool _sort(node x, node y) {

}

int b[100010];

void build (int x, int l, int r) {

}

void update(int x,int u,int e) {

if(tree[x].l==u&&tree[x].r==u) { tree[x].sum+=e; tree[x].l=l, tree[x].r=r; if(l==r) return ; build(x*2, l, (l+r)/2); build(x*2+1, (l+r)/2+1, r); return (x.s

} } if(tree[x].l>u||tree[x].r

long long query(int x, int l ,int r) {

}

int main() {

freopen("1670.in", "r", stdin); freopen("1670.out", "w", stdout); int n, _max=-INF; scanf("%d", &n); for( int i=1; i=l&&tree[x].rr||tree[x].r

}

} update(1, a[i].w, 1); for(int i=1; i

#include

#include

#include

#include

#include

using namespace std;

const int INF=2100083647;

struct node

{

int l, r;

long long max;

}tree[400010];

int n;

long long ans;

long long a[100010];

void buildTree(int x,int l,int r)

{

tree[x].l=l, tree[x].r=r;

if( l==r) { tree[x].max=a[l]; return ; }

buildTree( x*2 , l , (l+r)/2);

buildTree( x*2+1, 1+((l+r)/2), r );

tree[x].max=max(tree[x*2].max,tree[x*2+1].max) ;

}

long long query( int x, int l, int r) {

if( tree[x].l >=l && tree[x].r

if( tree[x].l > r || tree[x].r

}

int erfen(int x) {

}

int main() {

freopen("1667.in","r",stdin); freopen("1667.out","w",stdout); int l=0, r=n+1; while(l+1=a[x]) r=mid; else l=mid;

scanf("%d", &n);

for(int i=1; i

buildTree( 1, 1, n);

for( int i=1; i

ans+=erfen(i)-i;

}

printf("%lld", ans);

return 0; }

1665圆盘

题目描述

桌面上有N 个转盘，从左到右排放，编号从1到N 。每个转盘只能显示0至9中的一个数字。每个转盘有一个小开关，按转盘上的开关，转盘的数字就会自动加1，（如果转盘的数字是9，那么按开关时，转盘的数字就会变成0 ）。

Luka 现在玩这个游戏，他有两张白纸。

Luka 重复以下的步骤m 次（注意：下面的3个步骤要次序执行）：

（1）选两个整数A 、 B (1 ≤ A ≤ B ≤ N) 并且把它们写到第一张白纸上。

（2）把编号在区间[A，B]内（包括A 、B ）的所有转盘显示的数字逐一的加起来，把结果写到第二张白纸上。

（3）对编号在区间[A，B]内（包括A 、B ）的转盘，都按一次开关。 做完M 次这样的操作后，请你输出第二张白纸的数据。

分析

这题还是十分水的，动态维护十颗线段树，第一次做没经验…… 下面堵上代码：

#include

#include

#include

#include

#include

using namespace std;

struct node {

int l, r, add; long long sum; int n[10];

}tree[2000010];

int N, M;

char a[2500010];

void build( int x, int l, int r) {

tree[x].l=l, tree[x].r=r;

if( l==r) { tree[x].sum=a[l]-'0'; tree[x].n[a[l]-'0']++; return ; }

build( x*2 , l ,(l+r)/2);

build( x*2+1,1+((l+r)/2), r );

tree[x].sum= tree[x*2].sum+ tree[x*2+1].sum;

for( int i=0; i

}

long long _dat( int x) {

long long Sum=0;

int t[12];

for( int i=0; i

for( int i=0; i

return Sum;

}

void pushdown(int x) {

tree[x].sum=_dat(x);

tree[ x*2 ].add+=tree[x].add;

tree[x*2+1].add+=tree[x].add;

//tree[ x*2 ].sum=_dat(x*2);

//tree[x*2+1].sum=_dat(x*2+1);

tree[x].add=0;

}

void update(int x,int l,int r,int k)

{

if( tree[x].l>=l && tree[x].r

tree[x].add+=k;

}

long long query( int x, int l, int r) {

}

int main() {

freopen("1665.in","r",stdin); freopen("1665.out","w",stdout); scanf("%d %d", &N, &M); scanf("\n"); for( int i=1; i r || tree[x].r =l && tree[x].r r || tree[x].r

}

}*/ } scanf("%d %d", &aa, &bb); for( int j=aa; j= 10) a[j]='0'; return 0; build(1, 1, N); } return 0; int aa, bb; for( int i=1; i

1667 发型

题意：有n 头奶牛，从左往右排，每头奶牛都有一个高度，最左边的奶牛往右看，只能看到比它矮的奶牛。求最左边的奶牛所能看到的奶牛数量。

思路：这题从题目可以看出数据具有单调性：往右看右边一旦出现第一头奶牛比它高，无论后面的奶牛高度是多少，肯定也看不到那些奶牛。根据它的单调性及数据范围，我们可以想到二分的方法。二分一头奶牛的位置，如果从最左边的奶牛到这头奶牛的区间内，如果最高奶牛的高度小于最左边奶牛的高度，就证明还可以看到更多的奶牛，

就把区间缩小到mid-R ，反之则缩小到L-mid 。求区间内的最大值，我们很自然地可以想到线段树，做一遍线段树，判断一下，修改区间就解决这题了。

时间复杂度O(n log n log n)

参考程序：

#include

#include

#include

#include

#include

using namespace std;

const int INF=2100083647;

struct node

{

int l, r;

long long max;

}tree[400010];

int n;

long long ans;

long long a[100010];

void buildTree(int x,int l,int r)

{

tree[x].l=l, tree[x].r=r;

if( l==r) { tree[x].max=a[l]; return ; }

buildTree( x*2 , l , (l+r)/2);

buildTree( x*2+1, 1+((l+r)/2), r );

tree[x].max=max(tree[x*2].max,tree[x*2+1].max) ;

}

long long query( int x, int l, int r) {

if( tree[x].l >=l && tree[x].r r || tree[x].r

}

int erfen(int x) {

}

int main() {

freopen("1667.in","r",stdin); freopen("1667.out","w",stdout); int l=0, r=n+1; while(l+1=a[x]) r=mid; else l=mid;

scanf("%d", &n);

for(int i=1; i

buildTree( 1, 1, n);

for( int i=1; i

ans+=erfen(i)-i;

}

printf("%lld", ans);

return 0;

}

1668. 垃圾桶

本题采用的是动态规划+线段树求最小值的算法，先将每个区间按开始点排序，再使用动态规划。使用f[i]表示清洁前i 个垃圾桶所需

最小费用maps[i]和mapt[i]表示以i 结尾的清洁工清洁的区间。可以推出状态转移方程：f[i]=min (每个在maps[i]和mapt[i]之间结尾的区间+所需费用，f[i]).

下面贴上部分代码：

int main()

{

freopen ("1668.in","r",stdin);

freopen ("1668.out","w",stdout);

long long m,l,r;

cin>>m>>l>>r;

r=r-l+1;

for (int i=1; i

{

cin>>stw[i].s>>stw[i].t>>stw[i].w;

stw[i].s-=l-1;

stw[i].t-=l-1;

}

sort (stw+1,stw+m+1,xx);

l=1;

build (1,0,r);

for (int i=0; i

{

maps[i]=m+1;

mapt[i]=0;

}

for (int i=m; i; i--) maps[stw[i].t]=i;

for (int i=1; i

update (1,0,f[0]=0);

for (int i=1; i

{ //头 //尾

}

} f[i]=INF; for (int j=maps[i]; j

1666 售票系统

题意：某次列车途经C 个城市，城市编号依次为1到C ，列车上共有S 个座位，每一个售票申请包含三个参数， O 为起点，D 为目的地站，N 为车票张数。售票系统对该售票申请受理或不受理的决定，只有在从O 到D 的区段内列车上都有N 个或N 个以上的空座位时该售票申请才被受理。请你写个程序，实现这个自动售票系统。

思路：求一个区间内的值的问题我们会想到线段树，因为它必须保证区段内都有那么多座位，所以我们要考虑最坏情况，即在线段树内记录该区间的最少座位数，每一次都要进行修改和维护

注意：这里有一个坑，就是终点站不能算入区间内，就是相当于把相邻两个车站之间连一条边，把边看成线段树。简单来说就是在输入时，加一句D - -。

参考程序：

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

long long s[60010],oo=2147483647;

int C,S,R,O,D,N;

struct data

{

long long sum,add;

}tree[4*60010];

void build(long long now, long long L, long long R)

{

if (L==R) {tree[now].sum=s[L];}

else

{

build(now*2,L,(L+R)/2);

build(now*2+1,(L+R)/2+1,R);

tree[now].sum=min(tree[now*2].sum,tree[now*2+1].sum);

}

}

void down(long long root, long long L, long long R)

{

int LS=root*2,RS=root*2+1,mid=(L+R)/2;

tree[LS].add+=tree[root].add;

tree[RS].add+=tree[root].add;

tree[LS].sum+=tree[root].add;

tree[RS].sum+=tree[root].add;

tree[root].add=0;

}

void update(long long now, long long L, long long R, int x, int y, int v)

{

if (x>R || y

if (x=R)

{

tree[now].add+=v; tree[now].sum+=v; return;

}

down(now,L,R);

update(now*2,L,(L+R)/2,x,y,v);

update(now*2+1,(L+R)/2+1,R,x,y,v);

tree[now].sum=min(tree[now*2].sum,tree[now*2+1].sum);

}

long long query(long long now, long long L, long long R, int x, int y) {

if (x>R || y

if (x=R) return tree[now].sum;

down(now,L,R);

return

min(query(now*2,L,(L+R)/2,x,y),query(now*2+1,(L+R)/2+1,R,x,y));

}

int main()

{

freopen("1666.in","r",stdin);

freopen("1666.out","w",stdout);

cin>>C>>S>>R;

for (int i=1; i

build(1,1,C);

for (int i=1; i

{

scanf("%d%d%d",&O,&D,&N); D--;

if (query(1,1,C,O,D)

else

{

update(1,1,C,O,D,-N);

cout

}

}

return 0;

}


相关文章

  • 总账往来核销操作流程V2.1

    • 总账--往来核销操作流程 1.概述: ............................................................................................. 2 2.具体操 ...查看


  • 超酷算法:用四叉树和希尔伯特曲线做空间索引

    • [摘要:本文出处:http://blog.jobbole.com/81106/跟着愈来愈多的数据战运用战地舆空间相干,空间索引变得越发紧张.但是,有用天查询地舆空间数据是相称大的挑衅,由于数据是两维] 原文出处:http://blog.jo ...查看


  • PowerHR宣传册

    • Thrivesoft Thrivesoft Thrivesoft 一.公司简介 洛阳赛威软件科技有限公司是一家高速成长的技术型公司.主要从事PowerHR电力人力资源管理软件的研发.咨询.实施及服务.不断为用户提供务实创新的应用解决方案.赛 ...查看


  • 出纳银行对账培训资料

    • 出纳银行对账 1. 银行日记账:每天录入或从出纳系统引入: A.凭证引入:在查询条件中,选中未引入的,然后把区间选择正确.组织,点确定.查询到记录后,选中需要引入的凭证,可以按SHIFT.CTRL多选,点引入到日记账.凭证一经引入就不能修改 ...查看


  • 百度面试题

    • 从搜索引擎版转过来的,挺有意思.大家多想想 +U 1 完成函数 size_t foo(unsigned int *a1, size_t al1, unsigned int* a2, size_t al2) 其中a1和a2都为无符号数组,al ...查看


  • 天猫.淘宝店铺会员设置与管理

    • 一.管好自己的顾客--会员关系管理 1.客户进入与成长路径 流量客户.询问客户和潜在客户都是需要发掘的客户,让他们变成购买客户,来提升店铺的回头率与转化率,购买客户进行二次购买,至此变成忠实客户,变成忠实客户之后,咱们就需要用到会员关系管理 ...查看


  • 如何网上购买火车票

    • 如何网上购买火车票?学生需要些什么? 首先你要确定你有一张学生证(后有磁卡,写明乘车区间) 然后你在12306注册时标明学生的账号. 在购票时会有选择,(成人票/学生票).记得选学生票(这个在12306注册添加联系人时就有,但到时你的联系人 ...查看


  • 云呼叫中心

    • 讯鸟启通宝产品介绍 版权声明 北京讯鸟软件有限公司拥有本文档的计算机软件著作权,遵守任何适用的著作权法是用户的责任.未经北京讯鸟软件有限公司的明确书面许可,无论出于何种目的,均不得以任何形式或借助任何手段(电子.机械.影印.录音或其他手段) ...查看


  • 车辆行车事故(故障)应急预案

    • 3车辆行车事故(故障)应急预案 3.1车辆转运行途中部件脱落应急预案 一. 信息传递 1.事件发生后,发现人员要立即向添乘干部报告,启动应急预案.如可能造成区间长时间停车或构成严重隐患的设备故障,添乘干部须立即向车间领导.安全生产指挥中心及 ...查看


热门内容