2018ICPC 焦作训练赛

刺骨的言语ヽ痛彻心扉 2023-10-11 13:27 47阅读 0赞

赛后总结:

先把所有的可做题放上线程，debug在线程上有题的时候永远下机找

宁愿机下多线程debug不要机下多线程空想题

A. 0:05:54 solved by hl

温暖的签到

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

B.3:57:18 solved by gbs

思维题  
要打倒两个敌人，那么必然先打倒一个，后打倒另一个  
设打倒第一个敌人 hp为hp\_1 打倒其需要花费回合turn\_1 第二个则是hp\_2 turn\_2 ，设turn\_sum = turn\_1 + turn\_2  
设F(x) = (1+x)\*x/2; 可以理解为前x回合造成的总伤害（包括溢出伤害）  
那么一定有F(turn\_1)>=hp\_1 F(turn\_sum)>=hp\_1 + hp\_2 否则总伤害不够

有一条性质  
计数列 1,2,3……n 的和为sum 那么对于任意的1<=k <=sum 那么一定存在一种取法，从数列中取出若干数，使和为k（一种取法：从n到1枚举，若可以取便取。直到和等于k）  
类似的，在攻击第一个敌人时，可以取出若干次攻击来攻击第二个敌人，那么不会有伤害溢出。  
由此容易推断出满足F(turn\_1)>=hp\_1 和F(turn\_sum)>=hp\_1 + hp\_2 的最小 turn\_1 和turn\_sum即是最优解，可以用二分来查找

分先攻A 和先攻B两种情况讨论，就可以得到受到的伤害最小（存在turn\_1 = turn\_sum的情况，但这种情况不处理貌似对解题也没有影响）

麻烦的是要输出字典序最小的攻击方案，这里分先攻A和先攻B两种情况

首先要计算如果前turn\_1轮全打第一个敌人的溢出伤害 over\_damage1 打完两个敌人最多溢出的伤害为over\_damage2  
可以知道over\_damage1 <turn\_1 否则可以提前一轮打败第一个敌人

假设在前turn\_1轮 期间对第二个敌人造成了 k1点伤害  
那么k1>=over\_damage1-over\_damage2 否则打败后一个敌人的时间要延后一轮 不是最优解  
那么有 over\_damage1-over\_damage2 <=k1 <=over\_damage1

如果先攻A  
若over\_damage1-over\_damage2<=0则 前turn\_1轮全攻A 后面的轮全攻B  
如果over\_damage1-over\_damage2>0，那么在前turn\_1轮必须对B造成伤害 索性造成over\_damage1的伤害，那么只要再第 over\_damage1 轮攻击一次B即可，前面已经证明了over\_damage1 <turn\_1  
此时B出现最靠后，字典序最小

如果先攻B  
在前turn\_1次攻击中 选择若干次攻击A  
此时同样有over\_damage1-over\_damage2 <=k1 <=over\_damage1  
此时还要用到上的的函数F(x) = (1+x)\*x/2  
找到最大的t 使得F(t) >=over\_damage1 ，如果不考虑over\_damage1-over\_damage2 <=k1这个条件  
那么答案必然是若干个A+若干个B+若干个A的形式 例如如AAABBBBAAAAA （否则，如果出现A在两个B之间，则可以把这个A左移，使得字典序变小）  
考虑到over\_damage1-over\_damage2 <=k1这个条件 在构造后如果不满足这个条件 ，那么把前面若干个连续的A最后一个A的位置右移即可

如果先攻A和先攻B，受到的总伤害相同，那么对于这两种情况都计算一下，然后比较字符串的大小

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include<stack>
    #include<math.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<ctime>
    #include<complex>
    #include<stdio.h>
    #include<algorithm>
    #include<map>
    #include<queue>
    using namespace std;
    typedef long long LL;
    const int mod =1e9+7;
    int hpa,hpb,atka,atkb;
    int hpab;
    int sum_turn;
    int a_turn;
    int a_re;
    int b_turn;
    int b_re;
    LL ap_damage;
    LL bp_damage;
    int sum_r;
    int give_up,give_down;
    int theover(int a)
    {
        int left1 = 0;
        int right1 = 70000;
    
        LL ans;
        while(right1 -left1>1)
        {
            int mid = (left1 +right1)/2;
            ans =1LL *mid*(mid+1)/2;
            if (ans >=a)
                right1 =mid;
            else
                left1 = mid;
        }
        return right1;
    }
    int theblow(int a)
    {
        int left1 = 0;
        int right1 = 70000;
        int mid;
        LL ans;
        while(right1 -left1>1)
        {
            int mid = (left1 +right1)/2;
            ans =1LL *mid*(mid+1)/2;
            if (ans <=a)
                left1 =mid;
            else
                right1 = mid;
        }
        return left1;
    }
    char ansa[100005];
    char ansb[100005];
    bool cmp1()
    {
        for (int i=0; i<sum_turn; i++)
        {
            if (ansa[i] < ansb[i])
                return true;
            if (ansa[i] > ansb[i])
                return false;
        }
        return true;
    }
    int main()
    {
        int t;
        cin >>t;
        while(t--)
        {
            scanf("%d%d%d%d",&hpa,&hpb,&atka,&atkb);
            hpab = hpa+hpb;
            sum_turn = theover(hpab);
            sum_r = 1LL * (sum_turn+1)*sum_turn/2 - hpab;
    
            a_turn = theover(hpa);
            a_re = 1LL *(a_turn +1)*a_turn /2-hpa;
    
            b_turn = theover(hpb);
            b_re = 1LL *(b_turn +1)*b_turn /2-hpb;
    
            ap_damage = 1LL*atka * a_turn + 1LL*sum_turn * atkb;
            bp_damage = 1LL*atkb * b_turn + 1LL*sum_turn * atka;
            bool if_a_first= false;
            bool if_b_c = false;
            if (a_turn == sum_turn)
                if_a_first = false;
            else if (b_turn == sum_turn)
                if_a_first = true;
            else if (ap_damage <= bp_damage)
            {
                if_a_first = true;
                if (ap_damage == bp_damage)
                {
                    if_b_c = true;
                }
            }
            else
                if_a_first = false;
            LL fin_ans;
            if (if_a_first)//A first
            {
                fin_ans = ap_damage;
                give_up = a_re;
                give_down = a_re - sum_r;
                for (int i=0; i<a_turn; i++)
                    ansa[i] ='A';
                for (int i=a_turn; i<sum_turn; i++)
                {
                    ansa[i] ='B';
                }
                ansa[sum_turn] = 0;
    
    
                if (give_down>0)
                {
                    ansa[give_up-1]='B';
                }
            }
            if (if_b_c || !if_a_first)
            {
                fin_ans = bp_damage;
                give_up = b_re;
                give_down = b_re - sum_r;
                for (int i=0; i<b_turn; i++)
                    ansb[i] ='B';
                for (int i=b_turn; i<sum_turn; i++)
                {
                    ansb[i] ='A';
                }
                ansb[sum_turn] = 0;
    
    
                int dt1 = theblow(b_re);
                for (int i =0; i<dt1; i++)
                    ansb[i] ='A';
                int now_have = dt1 * (dt1+1)/2;
                if (now_have <give_down)
                {
                    now_have = give_down -now_have;
                    ansb[dt1-1]='B';
                    ansb[dt1-1+now_have]='A';
                }
    
            }
            cout<<fin_ans<<' ';
            if (if_b_c)
            {
                if(cmp1())
                    printf("%s\n",ansa);
                else
                    printf("%s\n",ansb);
            }
            else if(if_a_first)
                printf("%s\n",ansa);
            else
                printf("%s\n",ansb);
        }
    
    
        return 0;
    }
    
    
    /*
    111
    5111111 11111116 12133215 251111111
    111
    5 15 5 25
    5 14 5 25
    5 13 5 25
    5 12 5 25
    3
    14 14 5 5
    14 14 5 5
    */

C.3:01:00(-1) solved by zcz

用四个变量维护当前棋子的最左边，最右边，最上边，最下边

由八皇后棋子摆法的特性可知 只有同时存在于最左(右)和最上(下)的棋子才有可能重叠。

与此同时用两个变量表示棋盘的移动代替棋子的移动

当询问！的时候，判断每两个边界重合部分有多少点

当询问？的时候，如果点在边界上，则横纵坐标和边界相同，否则往棋盘相反的方向移动(不在边界上表示还未接触过棋盘的边界，因此每次移动都是K步不存在碰撞)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    
    struct Point
    {
        int x,y,flag;
    };
    
    Point p[300005];
    int n,m;
    int C[5];
    
    int a[300005],b[300005];
    int L,R,U,D,l,r,u,d,tl,tr,tu,td,DX,DY;
    int yin[10];
    long long C2(long long a)
    {
        return a*(a-1)/2;
    }
    
    
    int main()
    {
        yin[3]=1;
        yin[8]=2;
        yin[4]=3;
        yin[6]=4;
        int T;
        cin>>T;
        while(T--)
        {
            cin>>n>>m;
            for(int i=0;i<=4;i++)   C[i]=0;
            for(int i=1;i<=n;i++)
            {
                scanf("%d%d",&p[i].x,&p[i].y);
                int t=p[i].x;
                p[i].x=p[i].y;
                p[i].y=n-t+1;
                p[i].flag=0;
                if(p[i].x==n)
                {
                    p[i].flag=1;
                }
                else if(p[i].x==1)
                {
                    p[i].flag=2;
                }
                if(p[i].y==1)
                {
                    C[yin[p[i].flag]*3]++;
                    p[i].flag=3;
                }
                else if(p[i].y==n)
                {
                    C[yin[p[i].flag*4]]++;
                    p[i].flag=4;
                }
                a[p[i].x]=i;
                b[p[i].y]=i;
            }
            l=L=tl=1;
            r=R=tr=n;
            d=D=td=1;
            u=U=tu=n;
            DX=DY=0;
            char s[2];
            int k;
            int flag1=0,flag2=0;
            while(m--)
            {
                scanf("%s",s);
                if(s[0]=='D')
                {
                    scanf("%d",&k);
                    DY-=k;
                    tu-=k;
                    td-=k;
                    tu=max(tu,1);
                    td=max(td,1);
                    if(D+k<=n)
                    {
                        D+=k;
                        U+=k;
                    }
                    else
                    {
                        D=n;
                        U=2*n-1;
                    }
                    if(flag1)   continue;
                    if(D>=u)
                    {
                        flag1=1;
                        continue;
                    }
                    if(D>d)
                    {
                        for(int i=d+1;i<=D;i++)
                        {
                            int j=b[i];
                            C[yin[p[j].flag*3]]++;
                            p[j].flag=3;
                        }
                        d=D;
                    }
                }
                else if(s[0]=='U')
                {
                    scanf("%d",&k);
                    DY+=k;
                    tu+=k;
                    td+=k;
                    tu=min(tu,n);
                    td=min(td,n);
                    if(U-k>=1)
                    {
                        U-=k;
                        D-=k;
                    }
                    else
                    {
                        U=1;
                        D=2-n;
                    }
                    if(flag1)   continue;
                    if(U<=d)
                    {
                        flag1=1;
                        continue;
                    }
                    if(U<u)
                    {
                        for(int i=u-1;i>=U;i--)
                        {
                            int j=b[i];
                            C[yin[p[j].flag*4]]++;
                            p[j].flag=4;
                        }
                        u=U;
                    }
                }
                else if(s[0]=='R')
                {
                    scanf("%d",&k);
                    DX+=k;
                    tl+=k;
                    tr+=k;
                    tl=min(tl,n);
                    tr=min(tr,n);
                    if(R-k>=1)
                    {
                        R-=k;
                        L-=k;
                    }
                    else
                    {
                        R=1;
                        L=2-n;
                    }
                    if(flag2)      continue;
                    if(R<=l)
                    {
                        flag2=1;
                        continue;
                    }
                    if(R<r)
                    {
                        for(int i=r-1;i>=R;i--)
                        {
                            int j=a[i];
                            C[yin[p[j].flag*1]]++;
                            p[j].flag=1;
                        }
                        r=R;
                    }
                }
                else if(s[0]=='L')
                {
                    scanf("%d",&k);
                    DX-=k;
                    tl-=k;
                    tr-=k;
                    tl=max(tl,1);
                    tr=max(tr,1);
                    if(L+k<=n)
                    {
                        L+=k;
                        R+=k;
                    }
                    else
                    {
                        L=n;
                        R=2*n-1;
                    }
                    if(flag2)   continue;
                    if(L>=r)
                    {
                        flag2=1;
                        continue;
                    }
                    if(L>l)
                    {
                        for(int i=l+1;i<=L;i++)
                        {
                            int j=a[i];
                            C[yin[p[j].flag*2]]++;
                            p[j].flag=2;
                        }
                        l=L;
                    }
                }
                else if(s[0]=='!')
                {
                    long long ans=0;
                    if(flag1&&flag2)
                    {
                        ans=C2(n);
                    }
                    else if(flag1)
                    {
                        ans=C2(l)+C2(n-r+1);
                    }
                    else if(flag2)
                    {
                        ans=C2(d)+C2(n-u+1);
                    }
                    else
                    {
                        ans=C2(C[1])+C2(C[2])+C2(C[3])+C2(C[4]);
                    }
                    printf("%lld\n",ans);
                }
                else if(s[0]=='?')
                {
                    scanf("%d",&k);
                    int ans1,ans2;
                    if(p[k].x<=l||flag2)
                    {
                        ans1=tl;
                    }
                    else if(p[k].x>=r)
                    {
                        ans1=tr;
                    }
                    else
                    {
                        ans1=p[k].x+DX;
                    }
                    if(p[k].y<=d||flag1)
                    {
                        ans2=td;
                    }
                    else if(p[k].y>=u)
                    {
                        ans2=tu;
                    }
                    else
                    {
                        ans2=p[k].y+DY;
                    }
                    int t=ans2;
                    ans2=ans1;
                    ans1=n-t+1;
                    printf("%d %d\n",ans1,ans2);
                }
            }
        }
    
        return 0;
    }

D.0:57:28(-1) solved by zcz

手推一下公式

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    
    double pi=3.14159265358979323;
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            double a,b,r,d;
            cin>>a>>b>>r>>d;
            double l=sqrt((a+r)*(a+r)+b*b);
            double ar=asin(b/l);
            d=d/180*pi;
            double ans;
            if(d>ar)
            {
                ans=l-r;
            }
            else
            {
                ans=l*cos(ar-d)-r;
            }
                printf("%.10lf\n",ans);
        }
    
        return 0;
    }

E.1:33:17 solved by gbs

容易想到要找到的数是前k个素数的乘积，且这个乘积<=n  
根据样例可以找到规律，每多乘上一个素数p，答案乘上p/(p+1)  
然后使用大数模板或者java，再gcd即可

对于每多乘上一个素数p，答案就乘上p/(p+1)的简略证明：  
每多乘上一个素数p 并联的电阻的个数就变为原来的两倍 这些新的电阻的倒数是原来对应电阻倒数的1/p  
那么所有电阻倒数和为原来倒数和的（1+p）/p 倒回来后为原来的p/(p+1)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include<stack>
    #include<math.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<ctime>
    #include<complex>
    #include<stdio.h>
    #include<algorithm>
    #include<map>
    #include<queue>
    using namespace std;
    typedef unsigned long long LL;
    const int mod =1e9+7;
    
    const int maxn = 1e3+15;
    bool vis[maxn+15];
    int prel[maxn/2+5];
    int time1[maxn/2+5];
    int pnum = 0;
    char an[105];
    int bn[105];
    int len1 ;
    void pre()
    {
        memset(vis,false,sizeof(vis));
        for (int i=2; i<maxn; i++)
        {
            if (!vis[i])
            {
                //cout<<i<<endl;
                prel[pnum++] = i;
                for (int j =i<<1; j<maxn; j+=i)
                {
                    vis[j] = true;
                }
            }
        }
    }
    LL gcd(LL a,LL b)
    {
        if (b == 0)
            return a;
        return gcd(b,a%b);
    }
    void fen(LL n,int tp1)
    {
        for (int i =0; i<pnum; i++)
        {
            if (n==1)
                return ;
            while(n%prel[i] ==0)
            {
                n/=prel[i];
                time1[i]+=tp1;
            }
        }
    }
    
    class bigint
    {
    public:
        int bnum;
        int an[105];
        bigint(int a = 0)
        {
            memset(an,0,sizeof(an));
            bnum = 1;
            an[0] = 0;
            if (a!= 0)
            {
                bnum = 0;
            }
            while(a)
            {
                an[bnum] = a%10;
                a/=10;
                bnum++;
            }
        }
        void mul(int a)
        {
            int jinwei = 0;
            for (int i=0; i<bnum; i++)
            {
                an[i] = an[i]*a+jinwei;
                //123112312
                jinwei = an[i]/10;
                an[i] =an[i]%10;
                if (jinwei >0)
                    bnum = max(i+2,bnum);
            }
        }
        void out()
        {
            for (int i=bnum-1; i>=0; i--)
            {
                printf("%d",an[i]);
            }
        }
    };
    
    
    bool op1(int pcd)
    {
        int tuiwei = 0;
        bool if_ok = false;;
        //cout<<"@"<<pcd<<endl;
        for (int i=len1-1; i>=0; i--)
        {
            bn[i] += tuiwei*10;
            tuiwei = bn[i]%pcd;
            bn[i] = bn[i]/pcd;
            //cout<<bn[i];
            if (bn[i]>0)
                if_ok = true;
        }//cout<<endl;
        return if_ok;
    
    }
    int main()
    {
        pre();
    
        int t;
        cin >>t;
        while(t--)
        {
            scanf("%s",an);
            len1 = strlen(an);
            for (int i=0; i<len1; i++)
            {
                bn[i] = an[len1-1-i]-'0';
                //cout<<bn[i]<<endl;
            }
    
            memset(time1,0,sizeof(time1));
            for (int i=0; i<pnum; i++)
            {
                //cout<<"ce"<<endl;
                if (op1(prel[i]))
                {
                    //cout<<"we"<<i<<endl;
                    fen(prel[i],1);
                    fen(prel[i]+1,-1);
                }
                else
                {
                    break;
                }
            }
            bigint fenzi(1),fenmu(1);
            for (int i=0; i<pnum; i++)
            {
                while(time1[i]>0)
                {
                    fenzi.mul(prel[i]);
                    --time1[i];
                }
                while(time1[i]<0)
                {
                    fenmu.mul(prel[i]);
                    ++time1[i];
                }
            }
            fenzi.out();
            cout<<"/";
            fenmu.out();
            cout<<endl;
        }
    
    
    
    
        return 0;
    }

F.3:37:54(-3) solved by hl

WA原因:1.上下蜂巢可能会出现-- 或者 --这样的通路 2.编号标多了RE

建完图就是一个裸BFS,建图比较麻烦，建议分奇数行和偶数行，用每个六边形的中点标识整个六边形，

奇数行中点是(x,5) (x,17) (x,29) .....

偶数行中点是(x,11) (x,23) (x,35)......

然后每个六边形与其他六边形的边就是两个六边形中点连线的中点，判一下是不是空格就可以了，注意上下因为是---,有一个空格就算联通，需要特判

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 3e6 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    int N,M,K;
    const int a[6][2] = {-1,-3,-1,3,1,-3,1,3,-2,0,2,0};
    map<PII,int>P;
    PII id[maxn];
    LL dp[maxn];
    char MAP[7010][7010];
    int cnt,S,T;
    int main(){
        int q; Sca(q);
        while(q--){
            int x,y; P.clear();
            Sca2(x,y); cnt = 0;
            y = 6 * y + 3; x = 4 * x + 3;
            for(int i = 3; i < x ; i += 4){
                for(int j = 5; j <= y; j += 12){
                    P[mp(i,j)] = ++cnt;
                    id[cnt] = mp(i,j);
                }
            }
            for(int i = 5; i < x; i += 4){
                for(int j = 11; j <= y ; j += 12){
                    P[mp(i,j)] = ++cnt;
                    id[cnt] = mp(i,j);
                }
            }
            getchar();
            for(int i = 1; i <= x; i ++){
                gets(MAP[i] + 1);
            }
            for(int i = 1; i <= x; i ++){
                for(int j = 1; j <= y; j ++){
                    if(MAP[i][j] == 'S') S = P[mp(i,j)];
                    else if(MAP[i][j] == 'T') T = P[mp(i,j)];
                }
            }
            for(int i = 1; i <= cnt; i ++){
                int X = id[i].fi,Y = id[i].se;
                if(MAP[X - 2][Y - 1] == ' ' || MAP[X - 2][Y] == ' ' || MAP[X - 2][Y + 1] == ' '){
                    MAP[X - 2][Y - 1] = MAP[X - 2][Y] = MAP[X - 2][Y + 1] = ' ';
                }
                if(MAP[X + 2][Y - 1] == ' ' || MAP[X + 2][Y] == ' ' || MAP[X + 2][Y + 1] == ' '){
                    MAP[X + 2][Y - 1] = MAP[X + 2][Y] = MAP[X + 2][Y + 1] = ' ';
                }
            }
            for(int i = 0; i <= cnt; i ++) dp[i] = INF;
            queue<int>Q; while(!Q.empty()) Q.pop();
            Q.push(S); dp[S] = 1;
            while(!Q.empty() && dp[T] == INF){
                int u = Q.front(); Q.pop();
                int X = id[u].fi,Y = id[u].se;
                for(int i = 0 ; i < 6; i ++){
                    if(P[mp(X + a[i][0] * 2,Y + a[i][1] * 2)] && MAP[X + a[i][0]][Y + a[i][1]] == ' '){
                        int v = P[mp(X + a[i][0] * 2,Y + a[i][1] * 2)];
                        if(dp[v] > dp[u] + 1){
                            dp[v] = dp[u] + 1;
                            Q.push(v);
                        }
                    }
                }
            }
            if(dp[T] == INF) dp[T] = -1;
            Prl(dp[T]);
        }
        return 0;
    }

I.0:25:19 solved by hl

策略画画就会发现是最左端取一个，最右端取一个，最左端取一个，最右端取一个......

pre表示当前左端取的数的下标和，cnt1表示左端取了多少数字

erp表示当前右边取的数的下表和，cnt2表示右端取了多少数字

一个数a\[l\]加入的贡献就是ans += a\[l\] \* cnt1 - pre + (erp - a\[l\] \* cnt2);

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

H.unsolved by hl

应该是后缀数组加上某不知名数据结构去维护子区间的答案

某数据结构没有顶住

转载于:https://www.cnblogs.com/Hugh-Locke/p/11310811.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif