高考报名时间2022年11月1日还剩 天 距离2023年6月7日高考还有 天
栏目分类:
子分类:
返回
名师互学网用户登录
名师互学网
快速导航关闭
当前搜索
当前分类
前沿技术 软件开发 系统运维 产品运营 生活办公 面试经验 考试题库
子分类
人工智能 大数据 云计算 区块链 物联网 深度学习 机器学习 NLP 计算机视觉 语音识别 其他 大数据系统 数据可视化 数据挖掘与分析 其他 Docker/k8s 虚拟化 云平台 其他 基本原理 数字货币 智能合约 EOS应用 其他 通讯技术 嵌入式开发 单片机 物联网应用 HarmonyOS 其他 后端开发 Web开发 移动开发 游戏开发 Python Java 架构设计 C/C++/C# PHP .Net Go语言 R语言
实用工具
学习工具 小学数学练习 字帖生成 在线画板 函数绘制 拼音字母表 在线词典 黄历查询 亲戚关系计算 安全期计算 中国历史 Excel函数 模拟请求 json格式化 浏览器指纹
热门搜索
路由器设置 木托盘 宝塔面板 儿童python教程 心情低落 朋友圈 vim 双一流学科 专升本 我的学校 日记学校 西点培训学校 汽修学校 情书 化妆学校 塔沟武校 异形模板 西南大学排名 最精辟人生短句 6步教你追回被骗的钱 南昌大学排名 清朝十二帝 北京印刷学院排名 北方工业大学排名 北京航空航天大学排名 首都经济贸易大学排名 中国传媒大学排名 首都师范大学排名 中国地质大学(北京)排名 北京信息科技大学排名
名师互学网 > IT > 软件开发 > 后端开发 > Java

Namomo Spring camp 2022 Div1 Day3学习笔记（数据结构：单调栈/离线询问）

Java 更新时间： 发布时间： IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Namomo Spring camp 2022 Div1 Day3学习笔记（数据结构：单调栈/离线询问）

建议先弄懂 T 2 T2 T2,考虑使用单调栈+线段树/树状数组在固定右端点的情况下维护任意一个左端点到右端点的区间最值。
代码风格不是平常的风格，平常代码一行只写一句，非常长所以放上来的时候

T0:Edu124 E. Sum of Matchings

上课前讲的一道近期cf题目 待补。

然后上课刚开始，dls大致介绍了一下树状数组上二分，待补。

T1:abc234_g Divide a Sequence

这道题的大致题意是，给定一个长为 n n n的数组，我们可以对他进行一个划分，每次划分的 v a l u e s values values是对所有部分的（最大值-最小值）进行累积。求所有划分的 v a l u e s values values的累和。

划分：在不删除、移动数组种任何元素的情况下，将数组分割成若干子数组如{[1,2,3]}可以划分成{[1],[2,3]}或{[1],[2],[3]}等

大致思路：容易得到
f ( i ) = ∑ j = 0 i − 2 f ( j ) ∗ m a x ( a [ j + 1 ] , . . , a [ i ] ) − ∑ j = 0 i − 2 f ( j ) ∗ m i n ( a [ j + 1 ] , . . . , a [ i ] ) f(i)=sum_{j=0}^{i-2}f(j)*max(a[j+1],..,a[i])-sum_{j=0}^{i-2}f(j)*min(a[j+1],...,a[i]) f(i)=∑j=0i−2​f(j)∗max(a[j+1],..,a[i])−∑j=0i−2​f(j)∗min(a[j+1],...,a[i])
然后考虑维护（ m i n min min维护和 m a x max max维护相同）
∑ j = 0 i − 2 f ( j ) ∗ m a x ( a [ j + 1 ] , . . , a [ i ] ) sum_{j=0}^{i-2}f(j)*max(a[j+1],..,a[i]) ∑j=0i−2​f(j)∗max(a[j+1],..,a[i])
这里的 m a x max max可以通过单调栈维护

AC code:

#include 
#define mod 998244353
#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
int n,k,m,cnt;
int a[300005];
int dp[300005];
stack s1,s2;
int tr[300005];

void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i)) (tr[i]+=k)%=mod;}
int qr(int x,int res=0){
    for(int i=x;i>0;i-=lowbit(i)) (res+=tr[i])%=mod;
    if(x>=0)(res+=1)%=mod;
    return res;
}
int ask(int l,int r){return (mod+qr(r)-qr(l-1))%mod;}

void solve(){
    cin>>n;dp[0]=1;
    for(int i=1;i<=n;i++){cin>>a[i];}
    s1.push(0);s2.push(0);
    int maxsum=0,minsum=0;
    for(int i=1;i<=n;i++){
        while(s1.top()!=0&&a[s1.top()]<=a[i]){
            int u=s1.top();s1.pop();
            int dx=ask(s1.top(),u-1);
            maxsum=(maxsum-dx*a[u]%mod+mod)%mod;
        }
        maxsum=(maxsum+ask(s1.top(),i)*a[i]%mod)%mod;
        s1.push(i);
        while(s2.top()!=0&&a[s2.top()]>=a[i]){
            int u=s2.top();s2.pop();
            int dx=ask(s2.top(),u-1);
            minsum=(minsum-dx*a[u]%mod+mod)%mod;
        }
        minsum=(minsum+ask(s2.top(),i)*a[i]%mod+mod)%mod;
        s2.push(i);
        dp[i]=(maxsum-minsum+mod)%mod;
        add(i,dp[i]);
    }
    cout< 
T2:CF1635F Closest Pair 

题目大意：给定
    
     
      
       
        n
       
      
      
       n
      
     
    n个点，每个点有一个
    
     
      
       
        
         x
        
        
         i
        
       
       
        ,
       
       
        
         w
        
        
         i
        
       
      
      
       x_i,w_i
      
     
    xi​,wi​（每个点按照
    
     
      
       
        
         x
        
        
         i
        
       
      
      
       x_i
      
     
    xi​从小到大给出）。对于任意两点，他们的
    
     
      
       
        v
       
       
        a
       
       
        l
       
       
        =
       
       
        ∣
       
       
        
         x
        
        
         i
        
       
       
        −
       
       
        
         x
        
        
         j
        
       
       
        ∣
       
       
        ∗
       
       
        (
       
       
        
         w
        
        
         i
        
       
       
        +
       
       
        
         w
        
        
         j
        
       
       
        )
       
      
      
       val=vert x_i-x_j vert *(w_i+w_j)
      
     
    val=∣xi​−xj​∣∗(wi​+wj​)。
 给定
    
     
      
       
        n
       
      
      
       n
      
     
    n个询问，求每个询问给定的
    
     
      
       
        [
       
       
        
         l
        
        
         i
        
       
       
        ,
       
       
        
         r
        
        
         i
        
       
       
        ]
       
      
      
       [l_i,r_i]
      
     
    [li​,ri​]中，
    
     
      
       
        v
       
       
        a
       
       
        l
       
      
      
       val
      
     
    val最小的点对
 

大致思路 ：
 

 
 
1.使用单调栈得出所有可以成为答案的点对,且需要证明能够成为答案的点对至多
     
      
       
        
         2
        
        
         n
        
       
       
        2n
       
      
     2n对
 2.考虑将所有提问离线按照右端点排序,并用树状数组/线段树维护区间最小值
 

 

①证明过程：在所有点按照
    
     
      
       
        x
       
      
      
       x
      
     
    x坐标排序的情况下，对于两个不同点
    
     
      
       
        (
       
       
        
         x
        
        
         1
        
       
       
        ,
       
       
        
         w
        
        
         1
        
       
       
        )
       
       
        ,
       
       
        (
       
       
        
         x
        
        
         2
        
       
       
        ,
       
       
        
         w
        
        
         2
        
       
       
        )
       
      
      
       (x_1,w_1),(x_2,w_2)
      
     
    (x1​,w1​),(x2​,w2​),若
    
     
      
       
        
         x
        
        
         1
        
       
       
        <
       
       
        
         x
        
        
         2
        
       
       
        &
       
       
        &
       
       
        
         w
        
        
         1
        
       
       
        ≥
       
       
        
         w
        
        
         2
        
       
      
      
       x_1 

AC code
 

#include 
#define mod 998244353
#define int long long
#define endl 'n'
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
using namespace std;
int n,l,r,k,m,cnt,q;
stack s;
int tr[1200005];
int fk[300005];

struct node {
    int l,r,id;
    bool operator <(const node &t)const{return r=ql&&r<=qr){tr[rt]=min(tr[rt],k);return;}
	if(mid>=ql)update(lson,ql,qr,k);
	if(mid=ql&&r<=qr) return tr[rt];
	if(mid>=ql)res=min(res,query(lson,ql,qr));
	if(mid>n>>q;
    build(1,1,n);
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
        while(!s.empty()&&a[s.top()].r>=a[i].r){
            ans[++cnt]={s.top(),i,0};
            s.pop();
        }
        if(!s.empty()) ans[++cnt]={s.top(),i,0};
        s.push(i);
    }
    for(int i=1;i<=q;i++){cin>>ask[i].l>>ask[i].r;ask[i].id=i;}
    sort(ask+1,ask+1+q);
    for(int i=1,j=1;j<=q&&i<=cnt+1;i++){
        while(j<=q&&(ask[j].r 
T3：洛谷P1972 HH的项链 

题目大意：不重要，自己点进去看
 

大致思路：
    
     
      
       
        T
       
       
        2
       
      
      
       T2
      
     
    T2中思路
    
     
      
       
        2
       
      
      
       2
      
     
    2的模板，离线询问后用树状数组/线段树维护区间性质。
 

AC code
 

#include 
#define mod 998244353
#define int long long
#define endl 'n'
#define lowbit(x) (x&(-x))
using namespace std;
int n,l,r,k,m,cnt;
int a[1000005],last[1000005];
stack s1,s2;
int tr[1000005];
int fk[1000005];
void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=k;}
int qr(int x,int res=0){for(int i=x;i>0;i-=lowbit(i)) res+=tr[i];return res;}
int ask(int l,int r){return (mod+qr(r)-qr(l-1))%mod;}
struct node {
    int l,r,id;
    bool operator <(const node &t)const{return r>n;for(int i=1;i<=n;i++){cin>>a[i];}
    cin>>m;for(int i=1;i<=m;i++){cin>>ans[i].l>>ans[i].r;ans[i].id=i;}
    sort(ans+1,ans+1+m);
    for(int i=1,j=1;j<=m&&i<=n;i++){
        add(i,1);
        if(last[a[i]]!=0){add(last[a[i]],-1);}
        last[a[i]]=i;
        while(j<=m&&ans[j].r==i){
            fk[ans[j].id]=ask(ans[j].l,ans[j].r);
            j++;
        }
    }
    for(int i=1;i<=m;i++){cout< 
T4:CF526F Pudding Monsters 

大致题意：给定一个 
    
     
      
       
        n
       
       
        ×
       
       
        n
       
      
      
       n times n
      
     
    n×n 的棋盘，其中有 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个棋子，每行每列恰好有一个棋子。
 

求有多少个 
    
     
      
       
        k
       
       
        ×
       
       
        k
       
      
      
       k times k
      
     
    k×k 的子棋盘中恰好有 
    
     
      
       
        k
       
      
      
       k
      
     
    k 个棋子。
 

题解：首先因为题目保证每行每列都有一个棋子，所以我们可以将点对降维存储为
    
     
      
       
        a
       
       
        [
       
       
        x
       
       
        ]
       
       
        =
       
       
        y
       
      
      
       a[x]=y
      
     
    a[x]=y。
 容易想到对于任意一个
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]区间内，假设区间最大值为
    
     
      
       
        m
       
       
        a
       
       
        x
       
       
        n
       
      
      
       maxn
      
     
    maxn,区间最小值是
    
     
      
       
        m
       
       
        i
       
       
        n
       
       
        n
       
      
      
       minn
      
     
    minn，那么对于这个区间，如果刚好每行每列有一个棋子，则满足
    
     
      
       
        m
       
       
        a
       
       
        x
       
       
        n
       
       
        −
       
       
        m
       
       
        i
       
       
        n
       
       
        n
       
       
        =
       
       
        r
       
       
        −
       
       
        l
       
      
      
       maxn-minn=r-l
      
     
    maxn−minn=r−l。将等式右边移到左边，变成
    
     
      
       
        (
       
       
        m
       
       
        a
       
       
        x
       
       
        n
       
       
        −
       
       
        m
       
       
        i
       
       
        n
       
       
        n
       
       
        )
       
       
        −
       
       
        (
       
       
        r
       
       
        −
       
       
        l
       
       
        )
       
       
        =
       
       
        0
       
      
      
       (maxn-minn)-(r-l)=0
      
     
    (maxn−minn)−(r−l)=0。题目转变为，求满足以上等式的区间数量。
 考虑固定右端点，当右端点固定为
    
     
      
       
        r
       
      
      
       r
      
     
    r的时候，我们只需要判断左端点选择
    
     
      
       
        1
       
      
      
       1
      
     
    1到
    
     
      
       
        r
       
      
      
       r
      
     
    r时对应区间的性质，我们需要一个数据结构，保证维护每次的点
    
     
      
       
        l
       
      
      
       l
      
     
    l到当前固定右端点的区间的性质。
 重看上述等式
    
     
      
       
        (
       
       
        m
       
       
        a
       
       
        x
       
       
        n
       
       
        −
       
       
        m
       
       
        i
       
       
        n
       
       
        n
       
       
        )
       
       
        −
       
       
        (
       
       
        r
       
       
        −
       
       
        l
       
       
        )
       
       
        =
       
       
        0
       
      
      
       (maxn-minn)-(r-l)=0
      
     
    (maxn−minn)−(r−l)=0，容易证明
    
     
      
       
        m
       
       
        a
       
       
        x
       
       
        n
       
       
        −
       
       
        m
       
       
        i
       
       
        n
       
       
        n
       
       
        ≥
       
       
        r
       
       
        −
       
       
        l
       
      
      
       maxn-minn geq r-l
      
     
    maxn−minn≥r−l，所以我们当等式等于
    
     
      
       
        0
       
      
      
       0
      
     
    0时，即是区间最小值，所以我们只需要维护区间最小值且等于0的个数。
 考虑维护上述等式
    
     
      
       
        4
       
      
      
       4
      
     
    4个变量
 1.
    
     
      
       
        r
       
      
      
       r
      
     
    r，当区间右端点
    
     
      
       
        r
       
      
      
       r
      
     
    r变成
    
     
      
       
        r
       
       
        −
       
       
        1
       
      
      
       r-1
      
     
    r−1时，所有的左区间对应的区间长度+1，我们只需要对线段树全部
    
     
      
       
        −
       
       
        1
       
      
      
       -1
      
     
    −1即可。
 2.
    
     
      
       
        l
       
      
      
       l
      
     
    l，显然，所有的
    
     
      
       
        l
       
      
      
       l
      
     
    l都是在每个节点上都是一个常量，是不会变化的，我们在建立线段树的时候直接确定即可。
 3.
    
     
      
       
        m
       
       
        a
       
       
        x
       
       
        n
       
      
      
       maxn
      
     
    maxn，表示区间
    
     
      
       
        l
       
      
      
       l
      
     
    l到
    
     
      
       
        r
       
      
      
       r
      
     
    r的区间最大值，可以通过单调栈+线段树维护。
 4.
    
     
      
       
        m
       
       
        i
       
       
        n
       
       
        n
       
      
      
       minn
      
     
    minn，同3。
 将上述操作实现之后在固定每个右端点，每次查
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [1,r]
      
     
    [1,r]的区间最小值且等于
    
     
      
       
        0
       
      
      
       0
      
     
    0的个数即可。
 复杂度
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        l
       
       
        o
       
       
        g
       
       
        n
       
       
        )
       
      
      
       O(nlogn)
      
     
    O(nlogn)
 AC code
 

#include 
#define mod 998244353
#define int long long
#define endl 'n'
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
using namespace std;
const int N = 100005;
string yes="YESn",no="NOn";
int n,op,l,r,k,m,q,ans;
stack s1,s2;
int a[300005];
int cnt[1200005],minx[1200005],tr[1200005],lazy[1200005];
void push_up(int rt){
    minx[rt]=min(minx[ls],minx[rs]);cnt[rt]=0;
    if(minx[rt]==minx[ls])cnt[rt]+=cnt[ls];
    if(minx[rt]==minx[rs])cnt[rt]+=cnt[rs];
}
void build(int rt,int l,int r){
	if(l==r){minx[rt]=l;cnt[rt]=1;return;}
	build(lson);build(rson);
	cnt[rt]=cnt[ls];minx[rt]=minx[ls];
}
void push_down(int rt){
    minx[ls]+=lazy[rt];minx[rs]+=lazy[rt];
    lazy[ls]+=lazy[rt];lazy[rs]+=lazy[rt];
    lazy[rt]=0;
}
void update(int rt,int l,int r,int ql,int qr,int k){
	if(l>=ql&&r<=qr){minx[rt]+=k;lazy[rt]+=k;return;}
    push_down(rt);
	if(mid>=ql)update(lson,ql,qr,k);
	if(mid=ql&&r<=qr) return cnt[rt];
    push_down(rt);
	if(mid>=ql)res+=query(lson,ql,qr);
	if(mid>n;s1.push(0);s2.push(0);
    for(int i=1;i<=n;i++){int x,y;cin>>x>>y;a[x]=y;}
    build(1,1,n);
    for(int i=1;i<=n;i++){
        update(1,1,n,1,n,-1);
        while(s1.top()!=0&&a[s1.top()]a[i]){
            int u=s2.top();s2.pop();
            update(1,1,n,s2.top()+1,u,a[u]-a[i]);
        }
        s1.push(i);s2.push(i);
        ans+=query(1,1,n,1,i);
    }
    cout< 
T5：CF765F Souvenirs 

题目大意：给定一个数组，
    
     
      
       
        q
       
      
      
       q
      
     
    q次询问，每次问
    
     
      
       
        【
       
       
        
         l
        
        
         i
        
       
       
        ,
       
       
        
         r
        
        
         i
        
       
       
        】
       
      
      
       【l_i,r_i】
      
     
    【li​,ri​】之间相差最近两个数的差值。
 简要题解：仍然是首先离线询问，考虑维护每个
    
     
      
       
        l
       
      
      
       l
      
     
    l到
    
     
      
       
        r
       
      
      
       r
      
     
    r区间的对应的答案存储到
    
     
      
       
        l
       
      
      
       l
      
     
    l上。
 权值线段树维护区间对应最大值(每次单点插入
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i]处插入
    
     
      
       
        i
       
      
      
       i
      
     
    i)
 线段树维护
    
     
      
       
        l
       
      
      
       l
      
     
    l到对应区间的最小值。
 考虑对于大于
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i]部分维护答案：
 首先在权值线段树中找到
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i]到
    
     
      
       
        1
       
       
        e
       
       
        9
       
      
      
       1e9
      
     
    1e9中最大的值，在线段树中对应位置更新为
    
     
      
       
        a
       
       
        [
       
       
        u
       
       
        ]
       
       
        −
       
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[u]-a[i]
      
     
    a[u]−a[i]，然后继续找到
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i]到
    
     
      
       
        (
       
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
       
        +
       
       
        a
       
       
        [
       
       
        u
       
       
        ]
       
       
        )
       
       
        /
       
       
        2
       
      
      
       (a[i]+a[u])/2
      
     
    (a[i]+a[u])/2区间内最大值，进行同样操作，知道找不到值或
    
     
      
       
        a
       
       
        [
       
       
        u
       
       
        ]
       
       
        =
       
       
        =
       
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[u]==a[i]
      
     
    a[u]==a[i]为止。
 对于小于
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i]部分维护同上。
 复杂度
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
       
        n
       
       
        )
       
      
      
       O(nlog^2n)
      
     
    O(nlog2n)
 

#include 
#define int long long
#define endl 'n'
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
using namespace std;
const int N = 100005;
int n,l,r,k,m,q,x;
int a[100005],ans[300005];
int tr[4000005],ls[4000005],rs[4000005],root,cnt;
int c[400005];//命名后面带1的是线段树维护区间最小值
void push_up1(int rt){c[rt]=min(c[rt<<1],c[rt<<1|1]);}
void update1(int rt,int l,int r,int k,int x){
    if(l==r) {c[rt]=min(c[rt],x);return;}
    if(mid>=k)update1(rt<<1,l,mid,k,x);
	if(mid=ql&&r<=qr)return c[rt];
    if(mid>=ql)res=min(res,query1(rt<<1,l,mid,ql,qr));
    if(mid=k)update(ls[rt],l,mid,k,x);
	if(mid=ql&&r<=qr) return tr[rt];
	if(mid>=ql)res=max(res,query(ls[rt],l,mid,ql,qr));
	if(mid>n;for(int i=1;i<=n;i++){cin>>a[i];}
    cin>>m;for(int i=1;i<=m;i++){cin>>ri[i].l>>ri[i].r;ri[i].id=i;}
    sort(ri+1,ri+1+m);
    update(root,0,1000000000,a[1],1);
    for(int i=2,j=1;i<=n&&j<=m;i++){
        int u=query(root,0,1000000000,a[i],1000000000),v=query(root,0,1000000000,0,a[i]);
        while(u){  
            update1(1,1,n,u,a[u]-a[i]);
            if(a[u]==a[i])break;
            u=query(root,0,1000000000,a[i],(a[i]+a[u])/2);//往靠近a[i]方向取整所以向下取整
        }
        while(v){
            update1(1,1,n,v,a[i]-a[v]);
            if(a[v]==a[i])break;
            v=query(root,0,1000000000,(a[v]+a[i]+1)/2,a[i]);//往靠近a[i]方向取整所以向上取整
        }
        update(root,0,1000000000,a[i],i);
        while(j<=m&&ri[j].r==i){
            int cao=query1(1,1,n,ri[j].l,i);
            ans[ri[j].id]=cao;
            j++;
        }
    }
    for(int i=1;i<=m;i++){cout< 
T6:CF438D The Child and Sequence 

题目大意：给一个数组，支持区间取模，单点修改，查区间和。
 

题目思路：首先对三个操作写一个暴力，区间求和与单点修改操作都是基本线段树操作，直接套板子即可。所以考虑区间取模。
 考虑一个简单的剪枝，假设输入的模数为
    
     
      
       
        k
       
      
      
       k
      
     
    k，对于区间内的所有点，只有大于
    
     
      
       
        k
       
      
      
       k
      
     
    k的数会遭受修改，而所有比k小的数都是不变的，所以在线段树上，我们统计一个区间
    
     
      
       
        m
       
       
        a
       
       
        x
       
      
      
       max
      
     
    max,如果区间
    
     
      
       
        m
       
       
        a
       
       
        x
       
       
        <
       
       
        k
       
      
      
       max 这是一个非常暴力的写法，但是我们只需要增加一个这个判断即可通过这题。
 粗略证明：考虑到取模操作 ，容易证明在
    
     
      
       
        a
       
       
        ≤
       
       
        k
       
      
      
       aleq k
      
     
    a≤k的情况下 
    
     
      
       
        a
       
       
        %
       
       
        k
       
       
        <
       
       
        
         a
        
        
         2
        
       
      
      
       a % k < frac a2
      
     
    a%k<2a​（可以结合
    
     
      
       
        g
       
       
        c
       
       
        d
       
      
      
       gcd
      
     
    gcd的复杂度证明莱思考），所以对任意一点，取模操作至多
    
     
      
       
        l
       
       
        o
       
       
        g
       
      
      
       log
      
     
    log次，单点修改至多增加
    
     
      
       
        l
       
       
        o
       
       
        g
       
      
      
       log
      
     
    log次操作，所以整体操作次数不会超过
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        l
       
       
        o
       
       
        o
       
       
        g
       
       
        n
       
       
        )
       
      
      
       O(nloogn)
      
     
    O(nloogn)（还是
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
       
        n
       
       
        )
       
      
      
       O(nlog^2n)
      
     
    O(nlog2n)?不会进行复杂度分析，但是肯定是可以通过的复杂度）。
 AC code
 

#include 
#define int long long
#define endl 'n'
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
using namespace std;
int n,op,l,r,k,m,q,ans,x;
int a[100005];
int tr[400005],maxn[400005];
void push_up(int rt){tr[rt]=tr[ls]+tr[rs];maxn[rt]=max(maxn[ls],maxn[rs]);}
void build(int rt,int l,int r){
	if(l==r){cin>>tr[rt];maxn[rt]=tr[rt];return;}
	build(lson);build(rson);
    push_up(rt);
}
void update(int rt,int l,int r,int ql,int qr,int k){//单点修改为k，图省事直接用的区间修改写的单点修改
	if(l>=ql&&r<=qr){tr[rt]=maxn[rt]=k;return;}
	if(mid>=ql)update(lson,ql,qr,k);
	if(mid=ql&&r<=qr&&maxn[rt]=ql&&maxn[ls]>=k)update1(lson,ql,qr,k);
	if(mid=k)update1(rson,ql,qr,k);
	push_up(rt);
}
int query(int rt,int l,int r,int ql,int qr,int res=0){//查询区间和
	if(l>=ql&&r<=qr) return tr[rt];
	if(mid>=ql)res+=query(lson,ql,qr);
	if(mid>n>>q;build(1,1,n);
    while(q--){
        cin>>op;
        if(op==1){cin>>l>>r;cout<>l>>r>>x;update1(1,1,n,l,r,x);}
        else{cin>>k>>x;update(1,1,n,k,k,x);}
    }
}
signed main(){
    int t=1;
    while (t--)
        solve();
}

 

如果以上有错误之处可以评论指出。
转载请注明：文章转载自 www.mshxw.com
本文地址：https://www.mshxw.com/it/762445.html

Java相关栏目本月热门文章

热门相关搜索
路由器设置 木托盘 宝塔面板 儿童python教程 心情低落 朋友圈 vim 双一流学科 专升本 我的学校 日记学校 西点培训学校 汽修学校 情书 化妆学校 塔沟武校 异形模板 西南大学排名 最精辟人生短句 6步教你追回被骗的钱 南昌大学排名 清朝十二帝 北京印刷学院排名 北方工业大学排名 北京航空航天大学排名 首都经济贸易大学排名 中国传媒大学排名 首都师范大学排名 中国地质大学(北京)排名 北京信息科技大学排名 中央民族大学排名 北京舞蹈学院排名 北京电影学院排名 中国戏曲学院排名 河北政法职业学院排名 河北经贸大学排名 天津中德应用技术大学排名 天津医学高等专科学校排名 天津美术学院排名 天津音乐学院排名 天津工业大学排名 北京工业大学耿丹学院排名 北京警察学院排名 天津科技大学排名 北京邮电大学(宏福校区)排名 北京网络职业学院排名 北京大学医学部排名 河北科技大学排名 河北地质大学排名 河北体育学院排名
学习工具
代数计算器
三角函数
解析几何
立体几何
知识解答
教育知识
百科知识
生活知识
常识知识
写作必备
作文大全
作文素材
句子大全
实用范文
关于我们
关于我们
联系我们
网站地图
交流群

名师互学网交流群

名师互学网客服

名师互学网客服

名师互学网 版权所有 (c)2021-2022 ICP备案号：晋ICP备2021003244-6号

我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号：晋ICP备2021003244-6号