The 19th Zhejiang I. barbecue

The 19th Zhejiang I. Barbecue

The question ： Two classmates Putata and Budada Playing a game , Give a fixed length string at the beginning , There will be $m$ Time to ask , Give a range each time you ask $[l,r]$, That is, intercept from the original string $[l,r]$ Part of . From the first classmate Putata Start the operation , Each operation must remove a character from the beginning or end of the string , If the string before and after the operation becomes a palindrome string, the classmate of the operation will be judged negative , Ask every time you ask which student will win ？

Tip:

• If the first student gets the palindrome string at the beginning , Then you must lose the game .
• Otherwise, the first student will get a non palindrome string , Because if the substring becomes a palindrome string after the operation, it is also counted as the operation of the students to lose , Then the best plan for students in operation is Non palindrome $*$ Non palindrome
• This means that if the game is not over, that is, after the last operation, the string becomes Non palindrome , Then it means that if the game continues all the time The first operation , The students who operated got it Always a non palindrome string . Then through continuous operation , The final length is $2$ Classmate You will lose , Because no matter how you operate , The rest $1$ Characters must be Palindrome .
• So obviously, if the student who operated for the first time got Non palindrome And the length is even, then the student who operates for the first time will lose . If it is Non palindrome And the length is odd , Then the first operation of the students will win . Of course, there is a special case of non palindrome even digit strings $abababab$, Whether the first character or the last character is removed, the operator will input , So it is also classified into the first case .
• The next step is if the decision interval $[l,r]$ The string in is palindrome string , The queries given by the title are $10^6$, So the complexity of support is $O(1)$ Inquire about . Then we can use string $hash$ and $Manachar$ Algorithm . The string is given here $hash$ practice ( Study address ).

Code ：

#include<bits/stdc++.h>
using namespace std;
int n,q;
const int P = 131;
const int N = 1e6+10;
unsigned long long p[N],t[N],t1[N];
unsigned long long query1(int l,int r){
    
    return t[r]-t[l-1]*p[r-l+1];
}
unsigned long long query2(int l,int r){
    
    return t1[l]-t1[r+1]*p[r-l+1];
}
char s[N];
int main(){
    
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    p[0]=1;
    t[0]=0;
    t1[n+1]=0;
    for(int i=1;i<=n;i++){
    
        p[i]=p[i-1]*P;
        t[i]=t[i-1]*P+s[i];
    }
    for(int i=n;i>=1;i--){
    
        t1[i]=t1[i+1]*P+s[i];
    }
    while(q--){
    
        int l,r;
        scanf("%d%d",&l,&r);
        if(query1(l,r)==query2(l,r)){
    
            printf("Budada\n");
        }
        else{
    
            if((r-l+1)%2==0)printf("Budada\n");
            else printf("Putata\n");
        }
    }
    return 0;
}