洛谷P1901 发射站
某地有 N 个能量发射站排成一行，每个发射站 i 都有不相同的高度 Hi，并能向两边（当 然两端的只能向一边）同时发射能量值为 Vi 的能量，并且发出的能量只被两边最近的且比 它高的发射站接收。
显然，每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受，特别是为了安 全，每个发射站接收到的能量总和是我们很关心的问题。由于数据很多，现只需要你帮忙计 算出接收最多能量的发射站接收的能量是多少。
输入格式：
第 1 行：一个整数 N;
第 2 到 N+1 行：第 i+1 行有两个整数 Hi 和 Vi，表示第 i 个人发射站的高度和发射的能量值。
输出格式：
输出仅一行，表示接收最多能量的发射站接收到的能量值，答案不超过 longint。
这题跟洛谷P2947比较像，那个是只能向右边发射，这个加上左边就好了。
那么我们考虑只能向右边发射的情况，从右向左维护队首最大一个单调队列，如果队首就是当前元素，那么它没有可以辐射到的，因为他自己就是当前队列里最大的。
否则，因为当前元素在队尾，它之前那个元素一定是即离它最近又比他高，所以可以被他辐射到。
左边同理。。。
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct node{ int x,dfn; }team[1000001]; struct sz{ int h,v; }a[1000001]; long long n,m,tail,head; long long i,j,b[1000001]; long long ans[1000001],maxn; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch>‘9‘||ch<‘0‘){ if(ch==‘-‘) f=-1; ch=getchar();} while(ch<=‘9‘ && ch>=‘0‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } void write(long long x){ if(x<10){putchar(x%10+48); return;} write(x/10); putchar(x%10+48); } int main(){ n=read(); for (i=1; i<=n; i++) a[i].h=read(),a[i].v=read(); head=1; tail=1; team[head].x=a[n].h; team[head].dfn=n; b[n]=0; for (i=n-1; i>=1; i--){ while (head<=tail&&a[i].h>=team[tail].x) tail--; tail++; team[tail].x=a[i].h; team[tail].dfn=i; if (team[head].x<=a[i].h) b[i]=0; else{ b[i]=team[tail-1].dfn; ans[b[i]]+=a[i].v; } } head=1; tail=1; team[head].x=a[1].h; team[head].dfn=1; b[n]=0; for (i=2; i<=n; i++){ while (head<=tail&&a[i].h>=team[tail].x) tail--; tail++; team[tail].x=a[i].h; team[tail].dfn=i; if (team[head].x<=a[i].h) b[i]=0; else{ b[i]=team[tail-1].dfn; ans[b[i]]+=a[i].v; } } for (i=1; i<=n; i++) if (ans[i]>maxn) maxn=ans[i]; write(maxn); return 0; }
洛谷 P1823 [COI2007] Patrik 音乐会的等待
N个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。
写一个程序计算出有多少对人可以互相看见。
输入格式：
输入的第一行包含一个整数N (1 ≤ N ≤ 500 000), 表示队伍中共有N个人。
接下来的N行中，每行包含一个整数，表示人的高度，以毫微米(等于10的-9次方米)为单位，每个人的调度都小于2^31毫微米。这些高度分别表示队伍中人的身高。
输出格式：
输出仅有一行，包含一个数S，表示队伍中共有S对人可以互相看见。
这题其实单调队列并不难，但2018.6.29后加了三组数据，把我第一遍打的方法卡掉了，于是又写了一个记忆化过去了。
一开始循环里是这样的
for (i=n-1; i>=1; i--){ int x=tail; while (team[x]<=a[i]&&x>=head) x--; ans+=tail-x; if (team[x]>a[i]) ans++; while (head<=tail&&team[tail]<a[i]) tail--; tail++; team[tail]=a[i]; }
之后就会发现第一个while那里会被恶意数据卡掉，我们考虑优化。
设v[i]是i后面与i一样高的人的个数，初值是1。
这样我们在处理i时，可以把统计和弹出队尾元素放到一个while里，并且将相等的元素也弹出，v[i]+=v[j];
代码：
#include<cstdio> #include<iostream> using namespace std; struct node{ int h,v; }team[500001]; int i,n,head,tail; int j,a[500001]; long long ans; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch>‘9‘||ch<‘0‘){ if(ch==‘-‘) f=-1; ch=getchar();} while(ch<=‘9‘ && ch>=‘0‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int main(){ n=read(); for (i=1; i<=n; i++) a[i]=read(); head=1; tail=1; team[head].h=a[n]; team[head].v=1; for (i=n-1; i>=1; i--){ long long y=1; while (head<=tail&&team[tail].h<=a[i]){ ans+=team[tail].v; if (team[tail].h==a[i]) y+=team[tail].v; tail--; } if (team[tail].h>a[i]) ans++; tail++; team[tail].h=a[i]; team[tail].v=y; } printf("%lld",ans); return 0; }
原文：https://www.cnblogs.com/taduro/p/9470011.html
