CodeForces 1151E Number of Components

时间：2022-10-07 16:05:14

题目链接：http://codeforces.com/problemset/problem/1151/E

题目大意：

　　n个人排成一个序列，标号为 1~n，第 i 个人的学习成绩为 ai，现在要选出学习成绩在区间 [l, r] 中的人，被选出的人如果他们在序列中相邻，就将他们划分到一个小组，设 f(l, r) 表示一共可以分出的组的个数。求这个和：$ \sum_{l = 1}^n \sum_{r = 1}^n f(l, r) $。

分析：

　　对于每一个学生，都有作为它所在小组区间左端点和右端点的时候，每个点的贡献就是它作为左端点或右端点的次数，但我们并不需要都考虑，只需要单独考虑左端点(右端点)，这是因为这个点作为右端点的贡献恰好就是其他点作为左端点的贡献，把每个同学作为左端点的贡献累加起来就是答案。
　　对于 ai ，它是否能成为左端点是由 ai-1 的值所决定的：
当 ai-1 == ai 时，没有贡献，因为 ai 肯定不能成为左端点。
当 ai-1 > ai 时，区间端点必须满足 1 <= l <= ai ，ai <= r < ai-1 。贡献为 ai * (ai-1 - ai)。
当 ai-1 < ai 时，区间端点必须满足 ai-1 < l <= ai ，ai <= r <= n 。贡献为 (n - ai + 1) * (ai - ai-1)。

代码如下：

 #pragma GCC optimize("Ofast")

 #include <bits/stdc++.h>

 using namespace std;

 #define INIT() std::ios::sync_with_stdio(false);std::cin.tie(0);

 #define Rep(i,n) for (int i = 0; i < (n); ++i)

 #define For(i,s,t) for (int i = (s); i <= (t); ++i)

 #define rFor(i,t,s) for (int i = (t); i >= (s); --i)

 #define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i)

 #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i)

 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)

 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)

 #define pr(x) cout << #x << " = " << x << "  "

 #define prln(x) cout << #x << " = " << x << endl

 #define LOWBIT(x) ((x)&(-x))

 #define ALL(x) x.begin(),x.end()

 #define INS(x) inserter(x,x.begin())

 #define ms0(a) memset(a,0,sizeof(a))

 #define msI(a) memset(a,inf,sizeof(a))

 #define msM(a) memset(a,-1,sizeof(a))

 #define MP make_pair

 #define PB push_back

 #define ft first

 #define sd second

 template<typename T1, typename T2>

 istream &operator>>(istream &in, pair<T1, T2> &p) {

     in >> p.first >> p.second;

     return in;

 }

 template<typename T>

 istream &operator>>(istream &in, vector<T> &v) {

     for (auto &x: v)

         in >> x;

     return in;

 }

 template<typename T1, typename T2>

 ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) {

     out << "[" << p.first << ", " << p.second << "]" << "\n";

     return out;

 }

 typedef long long LL;

 typedef unsigned long long uLL;

 typedef pair< double, double > PDD;

 typedef pair< int, int > PII;

 typedef set< int > SI;

 typedef vector< int > VI;

 typedef map< int, int > MII;

 const double EPS = 1e-;

 const int inf = 1e9 + ;

 const LL mod = 1e9 + ;

 const int maxN = 1e5 + ;

 const LL ONE = ;

 const LL evenBits = 0xaaaaaaaaaaaaaaaa;

 const LL oddBits = 0x5555555555555555;

 LL n, a[maxN];

 LL ans;

 int main(){

     INIT();

     cin >> n;

     For(i, , n) cin >> a[i];

     For(i, , n) {

         if(a[i - ] < a[i]) ans += (a[i] - a[i - ]) * (n - a[i] + );

         else if(a[i - ] > a[i]) ans += a[i] * (a[i - ] - a[i]);

     }

     cout << ans << endl;

     return ;

 }

相关文章