NC206081. 最简单的一道题
描述
输入描述
第一行两个数字 n 和 m ， 表示数字个数和操作个数
第二行 n 个数字，表示建筑高度
后面 m 行指令：
或者：
数据范围：
输出描述
对于每个查询，输出答案，每个答案一行
示例1
输入:
5 5 1 2 3 4 3 q 3 c 1 3 3 q 2 c 5 5 4 q 5
输出:
1 2 0
C++14(g++5.4) 解法, 执行用时: 398ms, 内存消耗: 18408K, 提交时间: 2020-05-23 20:33:00
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int a[N];
int n, m, pos[N];
vector<int> vec;
namespace SegTree
{
#define ls (p<<1)
#define rs (p<<1|1)
struct seg
{
int l, r, len;
ll mn, tag;
}t[N<<2];
void setval(int p, ll v)
{
t[p].mn += v;
t[p].tag += v;
}
void pushdown(int p)
{
setval(ls, t[p].tag); setval(rs, t[p].tag);
t[p].tag = 0;
}
int ask2(int p, int x)
{
int l = t[p].l, r = t[p].r;
if(l==r) return t[p].mn;
if(t[p].tag) pushdown(p);
int mid = (l+r)>>1;
if(x<=mid) return ask2(ls, x);
else return ask2(rs, x);
}
int merge(int v, int p)
{
int l = t[p].l, r = t[p].r;
if(t[p].mn>v) return 0;
//if(ask2(1, l)<=v) return t[p].len;
if(l==r) return t[p].mn<=v;
if(t[p].tag) pushdown(p);
if(t[ls].mn>v) return merge(v, rs);
else return merge(v, ls) + t[p].len - t[ls].len;
}
void pushup(int p)
{
t[p].mn = min(t[ls].mn, t[rs].mn);
t[p].len = t[ls].len + merge(t[ls].mn, rs);
}
void build(int p, int l, int r)
{
t[p].l = l, t[p].r = r;
if(l==r)
{
t[p].mn = a[l];
t[p].len = 1;
pos[l] = p;
return;
}
int mid = (l+r)>>1;
build(ls, l, mid); build(rs, mid+1, r);
pushup(p);
}
void upd(int p, int x, int y, int v)
{
int l = t[p].l, r = t[p].r;
if(l>=x && r<=y)
{
setval(p, v);
return;
}
if(t[p].tag) pushdown(p);
int mid = (l+r)>>1;
if(x<=mid) upd(ls, x, y, v);
if(y>mid) upd(rs, x, y, v);
pushup(p);
}
void ask(int p, int x, int y)
{
int l = t[p].l, r = t[p].r;
if(l>=x && r<=y)
{
vec.pb(p);
return;
}
if(t[p].tag) pushdown(p);
int mid = (l+r)>>1;
if(x<=mid) ask(ls, x, y);
if(y>mid) ask(rs, x, y);
}
#undef ls
#undef rs
}
using namespace SegTree;
char op[2];
int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) scanf("%d", a+i);
build(1, 1, n);
for(int i=1; i<=m; i++)
{
scanf("%s", op);
if(op[0]=='c')
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
upd(1, l, r, k);
}
else
{
int x;
scanf("%d", &x);
vec.clear();
ask(1, x, n);
int ans = t[vec[0]].len;
ll mn = t[vec[0]].mn;
for(int i=1; i<sz(vec); i++)
{
ans += merge(mn, vec[i]);
mn = min(mn, t[vec[i]].mn);
}
printf("%d\n", ans-1);
}
}
return 0;
}
C++ 解法, 执行用时: 294ms, 内存消耗: 6292K, 提交时间: 2021-05-28 19:10:47
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n,m;
int a[N];
#define mid (l+r>>1)
#define ls o<<1
#define rs o<<1|1
int t[N<<2],laz[N<<2];
int g[N<<2];
void pd(int o){
if(laz[o]){
laz[ls]+=laz[o];
laz[rs]+=laz[o];
t[ls]+=laz[o];
t[rs]+=laz[o];
laz[o]=0;
}
}
int merge(int o,int l,int r,int x){
//找到这个区间
if(l==r)return t[o]<=x;
pd(o);
if(t[o]>x)return 0;
if(t[ls]>x)return merge(rs,mid+1,r,x);
return merge(ls,l,mid,x)+g[o]-g[ls];
}
void push_up(int o,int l,int r){
t[o]=min(t[ls],t[rs]);
g[o]=g[ls]+merge(rs,mid+1,r,t[ls]);//
}
void build(int o,int l,int r){
if(l==r){
t[o]=a[l];
g[o]=1;
return ;
}
build(ls,l,mid);
build(rs,mid+1,r);
push_up(o,l,r);
}
void up(int o,int l,int r,int x,int y,int d){
if(l>=x&&r<=y){
laz[o]+=d;
t[o]+=d;//
return ;
}
pd(o);
if(x<=mid)up(ls,l,mid,x,y,d);
if(y>mid)up(rs,mid+1,r,x,y,d);
push_up(o,l,r);
}
int getx(int o,int l,int r,int x){
if(l==r)return t[o];
pd(o);
int ans;
if(x<=mid)ans=getx(ls,l,mid,x);
else ans=getx(rs,mid+1,r,x);
push_up(o,l,r);
return ans;
}
int get(int o,int l,int r,int x,int y,int &val){
if(l>=x&&r<=y){
int ans=merge(o,l,r,val);
val=min(val,t[o]);
return ans;
}
pd(o);
int ans=0;
if(x<=mid)ans+=get(ls,l,mid,x,y,val);
if(y>mid)ans+=get(rs,mid+1,r,x,y,val);
push_up(o,l,r);
return ans;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",a+i);
build(1,1,n);
for(int i=1;i<=m;i++){
char x;
scanf(" %c",&x);
if(x=='c'){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
up(1,1,n,l,r,k);
}else{
int x;
scanf("%d",&x);
int d=getx(1,1,n,x);//
if(x+1<=n)printf("%d\n",get(1,1,n,x+1,n,d));
else puts("0");
}
}
return 0;
}