洛谷9月月赛II 赛后瞎写

看错比赛时间了....结果发现的时候已经开始了半个小时，并且当时正准备睡午觉qwq 于是就水了个t1就去睡跑了

写着写着然后看了一发评讲被辣鸡思路给绕了进去最后发现自己宛若一个智障

类似桶的思想直接用map映射一下向左倒和向右倒的杆子数量，若重合数为i, ans+=i*(i-1)/2;

就没了....

(去你的分类讨论

学了一波map的操作

　　建立：std:map<int,int> mmp;

　　赋值：mmp[i]=val;

　　遍历：for(map<int,int>::iterator i=mmp.begin();i!=mmp.end;i++)

　　查找：(1) 取key：i->first (2)取value：i->second

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<map>
 7 using namespace std;
 8 long long n,m,ans;
 9 std::map<long long,long long> mmp;
10 int main()
11 {
12     scanf("%lld%lld",&n,&m);
13     for(long long i=1;i<=n;i++)
14     {
15         long long k;
16         scanf("%lld",&k);
17         mmp[k+i]++;
18         mmp[i-k]++;
19     }
20     for(map<long long,long long>::iterator i=mmp.begin();i!=mmp.end();i++)
21         ans+=i->second*(i->second-1)/2;
22     printf("%lld",ans);
23     return 0;
24 }

View Code

那就先口胡一个了

恕我直言，这道题真的也太暴力了吧

维护A C之间的关系，我们用一个单调栈维护A的前缀最大值每次修改的时候直接把比修改值小的后面一部分删掉，并加入这个值可以找个数据结构来维护

维护B C之间的关系，用一个二维的数据结构一维维护乘积一维维护数量每次暴力修改？？？？

为防止乘积有零维护一个二元组{a,b}，这个数就表示为a*0^b

做乘法就是a1*a2,b1+b2;做除法就是a1/a2, b1-b2

然然然后就没了？？？？？？

智熄