Codeforces Global Round 7

A. Bad Ugly Numbers

put(2333...333)

B. Maximums

a[i]=b[i]=MAX;
MAX=max(MAX,a[i]);

C. Permutation Partitions

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=998244353;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n,k;
int p[N];
int pos[N]={0};
int main(){
   // IN
    cin>>n>>k;
    for(int i=0;i++<n;sc("%d",&p[i]));
    ll ans=0,res=1;
    for(int i=n;k;i--,k--)ans+=i,pos[i]=1;
    int last=0;
    for(int i=1;i<=n;i++){
        if(pos[p[i]]){
            if(!last){
                last=i;continue;
            }
            res=res*(i-last)%mod;
            last=i;
        }
    }
    cout<<ans<<" "<<res<<endl;
}

D1,D2. Prefix-Suffix Palindrome (Hard version)
找到前缀和后缀最长的，将中间的字符串拿出来找最长回文前缀，后缀，可以用KMP算法，hash,manacher或者回文树。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=2e6+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int L[N]={-1};
int kmp(const string& s){
    int i=0,j=-1,n=s.size();L[0]=-1;
    while(i<n)if(j==-1||s[i]==s[j])L[++i]=++j;else j=L[j];
    return L[n];
}
int main(){
   // IN
    int t;cin>>t;
    while(t--){
        string s;cin>>s;
        int l=0,r=(int)s.size()-1;
        if(r==0){
            O(s);continue;
        }
        while(l<r&&s[l]==s[r])l++,r--;
        string s1="",s2="";
        if(l)s1=s.substr(0,l),s2=s.substr(r+1);
        s=s.substr(l,r-l+1);string t=s;reverse(t.begin(),t.end());
        string a=s+"1"+t,b=t+"1"+s;
        string x=s.substr(0,kmp(a));
        string y=t.substr(0,kmp(b));
        if(x.size()<y.size())swap(x,y);
        cout<<s1<<x<<s2<<endl;
    }
}

E. Bombs

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=3e5+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n;
int p[N],q[N];
int pos[N];
struct sigment{
    int MAX[N*4+1],add[N*4+1];
    void push(int rt){
        if(add[rt]){
            add[rt<<1]+=add[rt];
            add[rt<<1|1]+=add[rt];
            MAX[rt<<1]+=add[rt];
            MAX[rt<<1|1]+=add[rt];
        }
        add[rt]=0;
    }
    void up(int l,int r,int val,int rt=1,int L=1,int R=n){
        if(L>=l&&R<=r){
            add[rt]+=val;
            MAX[rt]+=val;
            return;
        }
        push(rt);
        int mid=L+R>>1;
        if(mid>=l)up(l,r,val,rt<<1,L,mid);
        if(mid<r)up(l,r,val,rt<<1|1,mid+1,R);
        MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
    }
}T;
int main(){
    cin>>n;
    for(int i=0;i++<n;sc("%d",&p[i]),pos[p[i]]=i);
    for(int i=0;i++<n;sc("%d",&q[i]));
    int ans=n;T.up(1,pos[n],1);
    for(int i=1;i<=n;i++){
        pr("%d ",ans);
        if(i==n)return O("");
        T.up(1,q[i],-1);
        while(T.MAX[1]<=0)T.up(1,pos[--ans],1);
    }
}