题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla
#include<bits/stdc++.h>
using namespace std;

int main()
{
    vector<int>q,p,use;
    int n;
    cin >> n;

    q.push_back(0);
    for(int i = 1; i <= n; i++)
    {
        int s;
        cin >> s;
        if(s < 0)q.push_back(i);
        else p.push_back(i);
    }
    q.push_back(n + 1);

    long long res = 0;

    long long total = (n + 1) * n / 2;

    int m = q.size();
    for(int i = 0;i < m - 1;i ++)
    {
        if(i%2!=0)continue;

        if(i == 0)
            // i= 0 不包含
            for(int j = i + 1; j < m; j ++)
            {
                if(q[j] == 1)continue;
                int num = max(q[j]-1,1) - q[j-1];
                res += (num + 1) * num / 2;
                //cout << i << ' ' << res << ' ' << q[j] << ' ' << num << ' ' << endl; 
            }
        else
        {
            //i = 2 包含两个及以上
            for(int j = i + 1; j < m; j ++)
            {
                int num1 = q[j] - q[j - 1];
                int num2 = q[j - i] - q[j - i - 1];
                res += num1 * num2;
            }
        }
    }

    cout << total - res << ' ' << res;

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int dp[n+10][2];
    long long res_l = 0,res_r = 0;
    dp[0][0] = 0;
    dp[0][1] = 0;

    for(int i = 1; i <= n;i ++)
    {
        int c;
        cin >>c;
        if(c > 0)
        {   
            //0为正，1为负
            dp[i][0] = dp[i-1][0] + 1;
            dp[i][1] = dp[i-1][1];
        }
        else
        {
            dp[i][0] = dp[i-1][1];
            dp[i][1] = dp[i-1][0] + 1;
        }
        res_l += dp[i][0];
        res_r += dp[i][1];
    }

    cout << res_r << ' ' << res_l << endl;

    return 0;