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]，从l+1开始到b数组内里第一次出现大于等于2的数之间，肯定是之间加上a数组内里的数更加优秀，那么这一段区间的和怎么维护呢？因为操纵一会修改a数组，以是需要可以满足区间查询，单点修改的数据结构，那么就是树状数组。这样操纵一就完成。
考虑如何快速的找到b数组内里大于等于2的数的位置?可以使用链表来维护，链表的寄义是当前位置的b数组值大于等于2的下一个大于等于2的位置，这样的话，就可以先找到[l,r]区间内里第一个大于等于2的位置，然后不断的往反面跳跃，直到大于r。那么怎么快速的找到第一个位置呢？可以想打把每一个节点的位置塞到set内里，然后二分的查找就可以了。这样操纵三就完成了。
对于操纵二来说，因为是用链表来写的，以是如果改变的值大于等于2，那么就把改变的位置加入链表，如果小于2，并且b数组这个位置大于2，那么就把这个节点舍弃。如何快速的找当前点之前的呢，还是在set内里二分。

1. //冷静，冷静，冷静
2. //调不出来就重构
3. //#pragma GCC optimize(2)
4. //#pragma GCC optimize("O3")
5. #include<bits/stdc++.h>
6. #define endl '\n'
7. using namespace std;
8. typedef long long ll;
9. typedef long double ld;
10. typedef pair<ll,ll> pii;
11. const int N=1e6+10,mod=1000000007;
12. ll a[N],b[N],r[N],tree[N],l[N];
13. ll lowbit(ll x)
14. {
15.         return x&(-x);
16. }
17. ll query(ll x)
18. {
19.         ll sum=0;
20.         while(x)
21.         {
22.                 sum+=tree[x];
23.                 x-=lowbit(x);
24.         }
25.         return sum;
26. }
27. void updata(ll x,ll n,ll vel)
28. {
29.         while(x<=n)
30.         {
31.                 tree[x]+=vel;
32.                 x+=lowbit(x);
33.         }
34. }
35. void Jiuyuan()
36. {
37.         ll n;cin>>n;
38.         for(int i=1;i<=n;i++)//读入a,并且更新树状数组
39.         {
40.                 cin>>a[i];
41.                 updata(i,n,a[i]);
42.         }
43.         for(int i=1;i<=n;i++)cin>>b[i];
44.         ll id=n+1;
45.         set<ll> op;
46.         for(int i=n;i;i--)//建立双向链表
47.         {
48.                 if(b[i]>=2)
49.                 {
50.                         r[i]=id;
51.                         l[id]=i;
52.                         op.insert(id);
53.                         id=i;
54.                 }
55.         }
56.         r[0]=id;
57.         l[id]=0;
58.         op.insert(id);
59.         ll q;cin>>q;
60.         while(q--)
61.         {
62.                 ll nm;cin>>nm;
63.                 if(nm==1)
64.                 {
65.                         ll wz,x;cin>>wz>>x;
66.                         updata(wz,n,-a[wz]+x);
67.                         a[wz]=x;
68.                 }
69.                 else if(nm==2)
70.                 {
71.                         ll wz,x;cin>>wz>>x;
72.                         ll hj=*op.lower_bound(wz);//先找到大于等于x的位置，然后这个位置之前的一个，那么wz就会被夹在中间
73.                         hj=l[hj];
74.                         if(x>=2)
75.                         {
76.                                 ll a=hj,b=wz,c=r[hj];
77.                                 if(c==wz)c=r[c];//如果本身就是大于等于2，那么就需要在多跳一次
78.                                 r[a]=b;l[b]=a;
79.                                 r[b]=c;l[c]=b;
80.                                 op.insert(wz);
81.                         }
82.                         else
83.                         {
84.                                 if(b[wz]>=2)
85.                                 {
86.                                         ll a=hj,b=wz,c=r[hj];
87.                                         if(c==wz)c=r[c];
88.                                         r[a]=c;
89.                                         l[c]=a;
90.                                         op.erase(wz);
91.                                 }
92.                         }
93.                         b[wz]=x;
94.                 }
95.                 else
96.                 {
97.                         ll x,y;cin>>x>>y;
98.                         ll cs=a[x];
99.                         x++;
100.                         ll hj=*op.lower_bound(x);//找到第一个大于等于x并且满足要求的位置
101.                         while(hj<=y)
102.                         {
103.                                 ll xx=x,yy=hj-1;
104.                                 if(yy>=xx)//如果中间有b数组为1的区间，那么就加上a数组的值
105.                                 {
106.                                         cs+=query(yy);
107.                                         cs-=query(xx-1);
108.                                 }
109.                                 cs=max(cs+a[hj],cs*b[hj]);//1*6 1+6 明显后者更好，所以比较一下
110.                                 x=hj+1;
111.                                 hj=r[hj];
112.                         }
113.                         cs+=query(y);//如果有多余的，那么就加上a数组的值
114.                         cs-=query(x-1);
115.                         cout<<cs<<endl;
116.                 }
117.         }
118. }
119. int main()
120. {
121.         ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
122.         ll T=1;
123. //        cin>>T;
124.         while(T--)
125.         {
126.                 Jiuyuan();
127.         }
128.     return 0;
129. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。