Marvelous Necklace Gym - 102020M

M - Marvelous Necklace

 Gym - 102020M 

&：前缀和。

#include <cstdio>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char s[200005];
struct node
{
    int A,B;
} t[200005];
int main()
{
    int a,b;
    while(~scanf("%s", s))
    {
        memset(t,0,sizeof(t));
        int n = strlen(s);
        a = 0;
        b = 0;
        for(int i = 0; i < n; i ++)
        {
            if(s[i] == 'A') a++;
            else if(s[i] == 'B')b++;
        }
        for(int i = n; i < n * 2; i ++)
        {
            s[i] = s[i - n];
        }
        if(a % 2 != 0 || b % 2 != 0)
        {
            printf("NO\n");
        }
        else
        {
            int idx,idy;
            int A, B;
            A = 0;
            B = 0;
            idx = idy = 0;
            for(int i = 0; i < 2 * n; i ++)
            {
                if(s[i] == 'A')
                {
                    if(i == 0)
                    {
                        t[i].A ++;
                        t[i].B = 0;
                    }
                    else
                    {
                        t[i].A ++;
                        t[i].A += t[i - 1].A;
                        t[i].B = t[i - 1].B;
                    }
                }
                else if(s[i] == 'B')
                {
                    if(i == 0)
                    {
                        t[i].B ++;
                        t[i].A = 0;
                    }
                    else
                    {
                        t[i].B ++;
                        t[i].B += t[i - 1].B;
                        t[i].A = t[i - 1].A;
                    }
                }
            }

            for(int i = n; i < n * 2; i ++)
            {
                t[i].A -= t[i - n].A;
                t[i].B -= t[i - n].B;
            }

            int flag = 0;

           for(int i = n / 2; i < 2 * n; i ++)
            {
                if(t[i].A - t[i - n/2].A== a / 2 &&  t[i].B - t[i - n / 2].B == b / 2)
                {
                    flag = 1;
                    idx = i;
                    break;

                }
            }

            if(!flag) printf("NO\n");
            else
            {
                idx += 2;
                if(idx > n) idx = 1;
                idy = idx + n/ 2;
                if(idy > n) {idy = idy - n;}
                int dx = min(idx,idy);
                int dy = max(idx,idy);
                printf("YES\n%d %d\n",dx,dy);
            }
        }
    }
    return 0;
}