常州集训DAY7

又寄了
有个非常抽象的事，今天出题人把T1文件名打错了然后测评时全员爆零，最后学长决定全部重测（本来就很慢了这下直接在上课时都没出结果）
T1 赛时直接拿50分走人。前30分可以直接暴力，而且可以通过统计走过的路径数直接判断是否有解(根据猜测当路径数大于n^2时无解)。这样30分到手了。而剩下的20分可以用DP（？）来解决。先预处理出f[i]表示当前i位是0的时候要使前i位变为1时所需要的次数。通过手搓样例可知f[i]=f[i-1]*2+i。然后就能直接线性求解了。其中ans+=a[i]?1:f[i-1]+i+1。然后就快乐地50分。其实正解思路也是这样，但我赛时漏看了一个条件:p[i]<=i。然后，然后就没然后了，痛失50分。所以正解大概时在我的思路上把原图处理成链然后就同样是跑线性的求解。
代码参上

#include
using namespace std;
int n,t,p[1000005],v,now,ans,f[1000005];
bool a[1000005];
int main()
{
    freopen("warmhole.in","r",stdin);
    freopen("warmhole.out","w",stdout);
    cin>>n;
    for(int i=1;i>a[i];
        scanf("%d",&a[i]);
    }
    for(int i=1;i>p[i];
        scanf("%d",&p[i]);
        if(p[i]!=1)
        {
            v=1;
        }
    }
    if(v==1||n0)
        {
//          cout<<now<<endl;
            t--;
            if(now==n)
            {
                cout<<ans%1710833<<endl;
                return 0;
            }
            if(a[now]==1)
            {
                a[now]=0;
                now++;
                ans++;
            }
            else
            {
                a[now]=1;
                now=p[now];
                ans++;
            }
        }
        cout<<"Poor X"<<endl;
        return 0;
    }
    else
    {
        f[1]=1;
        for(int i=2;i<=n;i++)
        {
            f[i]=2*f[i-1]+i;
            f[i]%=1710833;
        }
//      cout<<f[1]<<" "<<f[2]<<" "<<f[3]<<" "<<f[4]<<endl;
        for(int i=1;i<n;i++)
        {
            if(a[i]==0)
            {
                ans+=f[i-1];
                ans+=i+1;               
            }
            else
            {
                ans+=1;
            }
            ans%=1710833;
        }
        cout<<ans<<endl;
    }
}

T2 T2只有30分。但这30分好像没什么好说的？直接枚举每一个点然后bfs，和统计染色块是一样的。正解是倒序并查集，不会。

本来今天的主题应该是：
莫队

莫队板子题
简单来说莫队就是暴力的优化。它本质上还是用for来对答案统计。但为什么它能是nlogn的算法呢？其实就是因为它通过对输入数据排序来减少重复的计算。（这就能看出来它是个离线算法，所以要卡也很简单，加个强制在线就行了）。当然，因为是对输入数据排序，所以只有当询问数很大时会体现出优势。它的排序分两层，首先按一个端点所在的块排序，若是块一样就根据另一个端点的大小排序。并且根据基本不等式，可以轻易得知当分块数量为sqrt（n）时效果最佳。大概就是这样吧。贴个莫队通用板子
大多数莫队都能用这个来搞

for (int i = 1; i  Q[i].l) add(--l);
        while (r < Q[i].r) add(++r);
        while (l  Q[i].r) del(r--);
        ans[Q[i].id] = res;
    }