一、差分
1.洛谷P1083借教室 (NOIP2012) https://www.luogu.com.cn/problem/P1083
比较显然的一种做法 ： 求哪一天显然具有单调性，可以二分。那么每一次check的时候差分，总复杂度 O( n* log m )级别
code :
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 4;
int n,m;
ll r[maxn],s[maxn],t[maxn],d[maxn],tmp[maxn];
bool check(int x)
{
for(int i=1;i<=n;i++) tmp[i]=0;
for(int i=1;i<=x;i++) {
tmp[s[i]]-=d[i];
tmp[t[i]+1]+=d[i];
}
for(int i=1;i<=n;i++) {
tmp[i]+=tmp[i-1];
if(tmp[i]+r[i]<0) return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&r[i]);
for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&d[i],&s[i],&t[i]);
int l=1,r=m,mid,ans=m+1;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) r=mid-1,ans=min(ans,mid);
else l=mid+1;
}
if(ans!=m+1) printf("-1\n%d",ans);
else printf("0");
return 0;
} 学了一种做法 ：O( n + m ) 的优秀复杂度 。 先做完差分，然后检查是否都符合要求，如果不符合，从后往前撤回订单，直到符合的位置即为答案。 code :
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 4;
ll r[maxn],s[maxn],t[maxn],d[maxn],f[maxn];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&r[i]);
for(int i=1;i<=m;i++) {
scanf("%lld%lld%lld",&d[i],&s[i],&t[i]);
f[s[i]]+=d[i];
f[t[i]+1]-=d[i];
}
int now=m,ans=m+1;
ll sum=0;
for(int i=1;i<=n;i++) {
sum+=f[i];
if(sum>r[i]) {
while(sum>r[i])
{
f[s[now]]-=d[now];
f[t[now]+1]+=d[now];
if(s[now]<=i&&t[now]>=i) sum-=d[now];
now--;
}
ans=now+1;
}
}
if(ans==m+1) printf("0");
else printf("-1\n%d",ans);
return 0;
} 二、单调栈
1.一个被坑过的题，比较典型的单调栈 https://blog.nowcoder.net/n/94a66c4dd8b249cab23928ceecc0da8c
2.2019牛客多校第八场 A
题干 ：
链接：https://ac.nowcoder.com/acm/contest/888/A 来源：牛客网 Gromah and LZR entered the great tomb, the first thing they see is a matrix of size n×m , and the elements in the matrix are all 0 or 1. LZR finds a note board saying "An all-one matrix is defined as the matrix whose elements are all 1, you should determine the number of all-one submatrices of the given matrix that are not completely included by any other all-one submatrices". Meanwhile, Gromah also finds a password lock, obviously the password should be the number mentioned in the note board! Please help them determine the password and enter the next level.分析 ：
三、单调队列
1.经典题目——滑动窗口 https://www.luogu.com.cn/problem/P1886
分析 ：head和tail动动动，滑滑滑
code :
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn];
struct Node {
int v,id;
}q[maxn],Q[maxn]; //其实只要一个就行了
int main()
{
int n,k,head=1,tail=1;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
Q[1].v=q[1].v=a[1];
Q[1].id=q[1].id=1;
for(int i=1;i<=n;i++) {
while(head<=tail&&i-q[head].id>=k) head++;
while(head<=tail&&q[tail].v>=a[i]) tail--;
q[++tail].v=a[i];
q[tail].id=i;
if(i>=k) printf("%d ",q[head].v);
}
printf("\n");
tail=1,head=1;
for(int i=1;i<=n;i++) {
while(head<=tail&&i-Q[head].id>=k) head++;
while(head<=tail&&Q[tail].v<=a[i]) tail--;
Q[++tail].v=a[i];
Q[tail].id=i;
if(i>=k) printf("%d ",Q[head].v);
}
return 0;
} 
京公网安备 11010502036488号