此篇属于比赛题解集合(CF && AcWing Race)链接

欢迎留言讨论

cf round 853 C

CODE

#include<iostream>
#include<cstring>


typedef long long ll;
using namespace std;
const int N = 4e5 + 10;



int main()
{
    int t;cin >> t;
    while(t --)
    {
        ll start[N];
        //int end[N];
        ll leng[N];//leng[a[]]
        ll a[N];//all number  id ->a
        ll now_a[N];// pos -> a
        bool appear[N];
        memset(leng,0,sizeof leng);
        memset(appear,false,sizeof appear);

        int n,m;
        cin >> n >> m;
        for(int i = 1;i <= n;i ++)
        {
            cin >> a[i];
            now_a[i] = a[i];
            start[a[i]] = 0;
            appear[a[i]] = true;
        }

     //   cout << start[a[1]] << "**" <<endl;

        int cnt = n;
        for(int i = 1;i <= m;i ++)
        {
            int num;int pos;
            cin >> pos >> num;
           // cout << leng[now_a[pos]]<<"&&&" << endl;
            leng[now_a[pos]] += (i - start[now_a[pos]]);
            //cout << start[now_a[pos]] << "**" <<endl;
            //cout << leng[a[pos]] <<"pos" <<endl;

            now_a[pos] = num;
            start[num] = i;

            if(!appear[num])
            {
           // cout << "num" <<num <<"cnt" << cnt<< endl;
            appear[num] = true;
            cnt ++;
            a[cnt] = num;
            }
        }


       // cout << m << "m" << endl;
       // cout << leng[now_a[1]] <<"now" <<endl;

        for(int i = 1;i <= n;i ++)
            leng[now_a[i]] += m - start[now_a[i]] + 1;

        ll res = 0;
        for(int i = 1;i <= cnt;i ++)//cnt有问题
        {
            ll x = leng[a[i]];
            //cout << a[i] << "-----"  << x << endl;
           // int t = m + 1 - x;
            res += (x *(m + 1 - x) * 1LL + (x - 1) * x /2 * 1LL);
        }
        cout << res << endl;

        //cout << endl;
        //cout << endl;
    }
    return 0;
}

DP

DP solution for problem C.

Let 𝑐𝑛𝑡(𝑖,𝑘) be the number of times the number 𝑘 appears in the arrays 𝐴0,𝐴1,…,𝐴𝑖 and let 𝑑𝑝[𝑖] the sum of the values of the concatenations (𝐴𝑖,𝐴𝑗),0≤𝑗<𝑖.

When we go from the iteration (𝑖−1)-th to the 𝑖-th only changes the number 𝑎𝑝 to 𝑣, so, in the transition 𝑑𝑝[𝑖−1]→𝑑𝑝[𝑖] we only have to analyze how 𝑎𝑝 and 𝑣 affect the result.

Assume that the change is not yet made in 𝐴𝑖 (𝐴𝑖=𝐴𝑖−1), then 𝑑𝑝[𝑖]=𝑑𝑝[𝑖−1]+𝑛 (because (𝐴𝑖,𝐴𝑖−1) are equal, so just add 𝑛 to 𝑑𝑝[𝑖]). The change is made and for each 𝑎𝑝 in 𝐴0,𝐴1,…,𝐴𝑖−1 we add +1 to 𝑑𝑝[𝑖] (because 𝑎𝑝 doesn’t exist in 𝐴𝑖), and for each 𝑣 in 𝐴0,𝐴1,…,𝐴𝑖−1 we substract −1 from 𝑑𝑝[𝑖].

So, the transition is:

𝑑𝑝[0]=0, 𝑑𝑝[𝑖]=𝑑𝑝[𝑖−1]+𝑛+𝑐𝑛𝑡(𝑖−1,𝑎𝑝)−𝑐𝑛𝑡(𝑖−1,𝑣), 1≤𝑖≤𝑚
And the answer is:

𝑎𝑛𝑠=∑𝑚𝑖=1𝑑𝑝[𝑖]