ABC 368 G - Add and Multiply Queries
原题链接：G - Add and Multiply Queries题意：给出数组a和b，三种操纵，第一种：以 1 i x 的形式给出。用x更换ai。第二种：以 2 i x 的形式给出。用x取代 bi 。第三种：以3 l r的形式给出，初始值为0，从l到r每个位置上可以选择加上a，或者乘上b，输出最大值。
思绪：链表+set+树状数组+二分。标题中给出了答案的范围不会高出1e18，那么就可以知道每次第三种操纵的区间内里b数组大于等于2的数的数目不会大于63个。
因为初始值是0，以是第一次操纵肯定是选择a，从l+1开始到b数组内里第一次出现大于等于2的数之间，肯定是之间加上a数组内里的数更加优秀，那么这一段区间的和怎么维护呢？因为操纵一会修改a数组，以是需要可以满足区间查询，单点修改的数据结构，那么就是树状数组。这样操纵一就完成。
考虑如何快速的找到b数组内里大于等于2的数的位置?可以使用链表来维护，链表的寄义是当前位置的b数组值大于等于2的下一个大于等于2的位置，这样的话，就可以先找到区间内里第一个大于等于2的位置，然后不断的往反面跳跃，直到大于r。那么怎么快速的找到第一个位置呢？可以想打把每一个节点的位置塞到set内里，然后二分的查找就可以了。这样操纵三就完成了。
对于操纵二来说，因为是用链表来写的，以是如果改变的值大于等于2，那么就把改变的位置加入链表，如果小于2，并且b数组这个位置大于2，那么就把这个节点舍弃。如何快速的找当前点之前的呢，还是在set内里二分。
//冷静，冷静，冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1000000007;
ll a,b,r,tree,l;
ll lowbit(ll x)
{
return x&(-x);
}
ll query(ll x)
{
ll sum=0;
while(x)
{
sum+=tree;
x-=lowbit(x);
}
return sum;
}
void updata(ll x,ll n,ll vel)
{
while(x<=n)
{
tree+=vel;
x+=lowbit(x);
}
}
void Jiuyuan()
{
ll n;cin>>n;
for(int i=1;i<=n;i++)//读入a,并且更新树状数组
{
cin>>a;
updata(i,n,a);
}
for(int i=1;i<=n;i++)cin>>b;
ll id=n+1;
set<ll> op;
for(int i=n;i;i--)//建立双向链表
{
if(b>=2)
{
r=id;
l=i;
op.insert(id);
id=i;
}
}
r=id;
l=0;
op.insert(id);
ll q;cin>>q;
while(q--)
{
ll nm;cin>>nm;
if(nm==1)
{
ll wz,x;cin>>wz>>x;
updata(wz,n,-a+x);
a=x;
}
else if(nm==2)
{
ll wz,x;cin>>wz>>x;
ll hj=*op.lower_bound(wz);//先找到大于等于x的位置，然后这个位置之前的一个，那么wz就会被夹在中间
hj=l;
if(x>=2)
{
ll a=hj,b=wz,c=r;
if(c==wz)c=r;//如果本身就是大于等于2，那么就需要在多跳一次
r=b;l=a;
r=c;l=b;
op.insert(wz);
}
else
{
if(b>=2)
{
ll a=hj,b=wz,c=r;
if(c==wz)c=r;
r=c;
l=a;
op.erase(wz);
}
}
b=x;
}
else
{
ll x,y;cin>>x>>y;
ll cs=a;
x++;
ll hj=*op.lower_bound(x);//找到第一个大于等于x并且满足要求的位置
while(hj<=y)
{
ll xx=x,yy=hj-1;
if(yy>=xx)//如果中间有b数组为1的区间，那么就加上a数组的值
{
cs+=query(yy);
cs-=query(xx-1);
}
cs=max(cs+a,cs*b);//1*6 1+6 明显后者更好，所以比较一下
x=hj+1;
hj=r;
}
cs+=query(y);//如果有多余的，那么就加上a数组的值
cs-=query(x-1);
cout<<cs<<endl;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll T=1;
// cin>>T;
while(T--)
{
Jiuyuan();
}
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]