题解：AtCoder AT_awc0087_e Change of Assigned Interval

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：E - Change of Assigned Interval

【题目描述】

Takahashi and Aoki manageN NNtasks numbered from1 11toN NN.

For thei ii-th task, a symbolS i S_iSi​representing the person in charge and a work costP i P_iPi​are recorded. WhenS i S_iSi​isT, the person in charge is Takahashi; when it isA, the person in charge is Aoki.

Here,flippingthe assignment means changingTtoAandAtoT.

Q QQqueries are given.

For thej jj-th query, you may perform the following operation at most once. It is also permitted to not perform the operation.

Operation:Choose a pair of integers( l , r ) (l, r)(l,r)satisfyingL j ≤ l ≤ r ≤ R j L_j \leq l \leq r \leq R_jLj​≤l≤r≤Rj​, and flip the assignment of all tasks from thel ll-th to ther rr-th.

Consider the total work cost of tasks assigned to Aoki (A) among the tasks from theL j L_jLj​-th to theR j R_jRj​-th after the operation (or if no operation is performed). Find the minimum value of this total when the operation is chosen optimally.

Each query is independent. An operation in one query does not affect the original assignment/cost information or other queries.

高桥和青木管理着编号从1 11到N NN的N NN个任务。

对于第i ii个任务，记录了表示负责人符号S i S_iSi​和工作成本P i P_iPi​。当S i S_iSi​为T时，负责人是高桥；当S i S_iSi​为A时，负责人是青木。

这里，翻转分配意味着将T改为A，将A改为T。

给定Q QQ个查询。

对于第j jj个查询，你最多可以执行一次以下操作。也可以选择不执行操作。

操作：选择一对满足L j ≤ l ≤ r ≤ R j L_j \leq l \leq r \leq R_jLj​≤l≤r≤Rj​的整数( l , r ) (l, r)(l,r)，并翻转从第l ll个到第r rr个所有任务的分配。

考虑操作后（或不执行操作时），从第L j L_jLj​个到第R j R_jRj​个任务中分配给青木（A）的任务的总工作成本。求当操作选择最优时，这个总和的最小值。

每个查询是独立的。一个查询中的操作不会影响原始的分配/成本信息或其他查询。

【输入】

N NNQ QQ
S 1 S_1S1​P 1 P_1P1​
S 2 S_2S2​P 2 P_2P2​
⋮ \vdots⋮
S N S_NSN​P N P_NPN​
L 1 L_1L1​R 1 R_1R1​
L 2 L_2L2​R 2 R_2R2​
⋮ \vdots⋮
L Q L_QLQ​R Q R_QRQ​

• The first line containsN NN, the number of tasks, andQ QQ, the number of queries, separated by a space.
• The followingN NNlines give the information of each task.
• Thei ii-th of these lines containsS i S_iSi​, representing the person in charge of thei ii-th task, andP i P_iPi​, representing the work cost of that task, separated by a space.
• S i S_iSi​isTorA.
• The followingQ QQlines give the information of the queries.
• Thej jj-th of these lines contains the left endpointL j L_jLj​and right endpointR j R_jRj​of the range for thej jj-th query, separated by a space.

【输出】

PrintQ QQlines.

On thej jj-th line, print the answer to thej jj-th query as an integer.

【输入样例】

5 4 A 3 T 5 A 2 T 4 A 6 1 5 2 4 3 3 4 5

【输出样例】

5 0 0 0

【算法标签】

#线段树

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=100005;// 定义最大数组长度intn,q;// 数组长度n，查询次数qintsa[N],v[N];// 前缀和数组sa，线段树基础数组vintw[N];// 备用数组（此处未使用）structNode{intl,r;// 区间左右端点intsum,pre,suf,best;// 区间和、最大前缀和、最大后缀和、最大子段和}tr[N*4];// 线段树数组voidpushup(intu)// 向上更新节点信息{tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;// 区间和tr[u].pre=max(tr[u<<1].pre,tr[u<<1].sum+tr[u<<1|1].pre);// 最大前缀和tr[u].suf=max(tr[u<<1|1].suf,tr[u<<1|1].sum+tr[u<<1].suf);// 最大后缀和tr[u].best=max({tr[u<<1].best,tr[u<<1|1].best,tr[u<<1].suf+tr[u<<1|1].pre});// 最大子段和}voidbuild(intu,intl,intr)// 建立线段树{if(l==r)// 叶子节点tr[u]={l,r,v[l],v[l],v[l],v[l]};// 初始化else// 非叶子节点{tr[u]={l,r};// 初始化区间intmid=l+r>>1;// 计算中点build(u<<1,l,mid),build(u<<1|1,mid+1,r);// 递归建树pushup(u);// 更新节点信息}}Nodequery(intu,intl,intr)// 区间查询{if(tr[u].l>=l&&tr[u].r<=r)// 完全包含returntr[u];// 直接返回else// 不完全包含{intmid=tr[u].l+tr[u].r>>1;// 计算中点if(r<=mid)returnquery(u<<1,l,r);// 完全在左子树if(l>mid)returnquery(u<<1|1,l,r);// 完全在右子树Node left=query(u<<1,l,r);// 查询左子树Node right=query(u<<1|1,l,r);// 查询右子树Node res;// 合并结果res.sum=left.sum+right.sum;// 区间和res.pre=max(left.pre,left.sum+right.pre);// 最大前缀和res.suf=max(right.suf,right.sum+left.suf);// 最大后缀和res.best=max({left.best,right.best,left.suf+right.pre});// 最大子段和returnres;// 返回结果}}signedmain()// 主函数{cin>>n>>q;// 输入数组长度和查询次数for(inti=1;i<=n;i++)// 读取数组元素{chars;// 操作类型intp;// 操作数值cin>>s>>p;// 输入操作类型和数值sa[i]=sa[i-1]+(s=='A'?p:0);// 计算前缀和（只累加A类型的值）v[i]=(s=='A'?p:-p);// 设置线段树基础数组值}build(1,1,n);// 建立线段树while(q--)// 处理每个查询{intl,r;// 查询区间cin>>l>>r;// 输入查询区间intbase=sa[r]-sa[l-1];// 计算基础值（区间内A类型值的和）Node res=query(1,l,r);// 查询区间信息intmaxReduce=max(0LL,res.best);// 最大可减少值cout<<base-maxReduce<<endl;// 输出结果}return0;// 程序正常结束}

【运行结果】

5 4 A 3 T 5 A 2 T 4 A 6 1 5 5 2 4 0 3 3 0 4 5 0