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[i]，或者乘上b[i]，输出最大值。
思路：链表+set+树状数组+二分。题目中给出了答案的范围不会超过1e18，那么就可以知道每次第三种操作的区间里面b数组大于等于2的数的数量不会大于63个。
因为初始值是0，所以第一次操纵一定是选择a[l]，从l+1开始到b数组里面第一次出现大于等于2的数之间，肯定是之间加上a数组里面的数更加优秀，那么这一段区间的和怎么维护呢？因为操作一会修改a数组，所以需要可以满足区间查询，单点修改的数据结构，那么就是树状数组。这样操作一就完成。
考虑如何快速的找到b数组里面大于等于2的数的位置?可以使用链表来维护，链表的含义是当前位置的b数组值大于等于2的下一个大于等于2的位置，这样的话，就可以先找到[l,r]区间里面第一个大于等于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[N],b[N],r[N],tree[N],l[N];
ll lowbit(ll x)
{return x&(-x);
}
ll query(ll x)
{ll sum=0;while(x){sum+=tree[x];x-=lowbit(x);}return sum;
}
void updata(ll x,ll n,ll vel)
{while(x<=n){tree[x]+=vel;x+=lowbit(x);}
}
void Jiuyuan()
{ll n;cin>>n;for(int i=1;i<=n;i++)//读入a,并且更新树状数组 {cin>>a[i];updata(i,n,a[i]);}for(int i=1;i<=n;i++)cin>>b[i];ll id=n+1;set<ll> op;for(int i=n;i;i--)//建立双向链表 {if(b[i]>=2){r[i]=id;l[id]=i;op.insert(id);id=i;}}r[0]=id;l[id]=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[wz]+x);a[wz]=x;}else if(nm==2){ll wz,x;cin>>wz>>x;ll hj=*op.lower_bound(wz);//先找到大于等于x的位置，然后这个位置之前的一个，那么wz就会被夹在中间 hj=l[hj];if(x>=2){ll a=hj,b=wz,c=r[hj];if(c==wz)c=r[c];//如果本身就是大于等于2，那么就需要在多跳一次 r[a]=b;l[b]=a;r[b]=c;l[c]=b;op.insert(wz);}else{if(b[wz]>=2){ll a=hj,b=wz,c=r[hj];if(c==wz)c=r[c];r[a]=c;l[c]=a;op.erase(wz);}}b[wz]=x;}else{ll x,y;cin>>x>>y;ll cs=a[x];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[hj],cs*b[hj]);//1*6 1+6 明显后者更好，所以比较一下 x=hj+1;hj=r[hj];}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;
}