首页 > 代码库 > BZOJ 1012 线段树或单调队列
BZOJ 1012 线段树或单调队列
1012: [JSOI2008]最大数maxnumber
题意：两种操作：1、查询当前数列中末尾L个数中的最大的数；2、当前数列末尾插入一个数。
tags：水题
线段树
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define FF(i,a,b) for (int i=a;i<=b;i++)#define F(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 2e5+10;const ll inf=1e18;int M, k;ll D, tr[N<<2], t;void updata(int ro, int L, int R, int p, ll x){ if(L==R && L==p) { tr[ro]=(tr[ro]+x)%D; return ; } int mid=L+((R-L)>>1); if(p<=mid) updata(ro<<1, L, mid, p, x); else updata(ro<<1|1, mid+1, R, p, x); tr[ro]=max(tr[ro<<1], tr[ro<<1|1]);}ll query(int ro, int L, int R, int l, int r){ if(L==l && R==r) return tr[ro]; int mid=L+((R-L)>>1); if(r<=mid) return query(ro<<1, L, mid, l, r); else if(mid<l) return query(ro<<1|1, mid+1, R, l, r); else return max(query(ro<<1, L, mid, l, mid), query(ro<<1|1, mid+1, R, mid+1, r));}int main(){ scanf("%d %lld", &M, &D); ll x; char ch[10]; FF(i,1,M) { scanf("%s %lld", ch, &x); if(ch[0]==‘A‘) updata(1, 1, M, k+1, x+t), k++; else { t=query(1, 1, M, k-x+1, k); printf("%lld\n", t); } } return 0;}
单调队列 感觉单调队列比较玄。 注：单调队列一般在数列一端有最大(最小)比较的时候用。
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define FF(i,a,b) for (int i=a;i<=b;i++)#define F(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 2e5+10;int M, k;ll D, a[N], mx[N], t;int main(){ scanf("%d %lld", &M, &D); char ch[10]; ll x; FF(cas,1,M) { scanf("%s %lld", ch, &x); if(ch[0]==‘A‘) { a[++k]=(x+t)%D; F(i,k,0) { if(mx[i]<a[k]) mx[i]=a[k]; else break; } } else printf("%lld\n", t=mx[k-x+1]); } return 0;}
BZOJ 1012 线段树或单调队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。