D

博弈 逆序对 循环移位

两个人分别操作自己的排列$a,b$，每次可以交换两个元素，要求交换之后$\sum a_i{b}_i$变大。轮流进行，如果一个人没法操作了，就输了。

每次询问会把一个人的排列的一个区间循环移位，然后需要输出此时先手必胜还是必败

注意到$\sum a_i{b}_i$最大就是两个排列完全一样，进一步，越接近完全一样，式子就越大。所以一个人每次交换两个元素，想让式子变大，1必须是逐步排序的一个过程，也就是要至少消除一个逆序对。这里的逆序对，是把一个排列作为基准，计算另一个排列的逆序对。

手玩样例会发现，先手是否必胜，由初始逆序对的奇偶性决定。这有两个切入角度，一是这是博弈，博弈一个经典问题就是守恒量，守恒量里一个经典问题就是奇偶性，所以可以先找一下奇偶对答案的影响。另一个更严谨的分析是，$swap$操作，每次会使得逆序对奇偶反转，这是经典结论。也就是，初始和结束状态的逆序对奇偶都是确定的，每次一个人操作会反转奇偶性，那么初始逆序对是奇数，则先手必胜，反之先手必败。

到这里都简单，但问题是每次会对一个区间循环移位，然后问先手是否必胜。看起来很难办，但不要慌，注意到循环移位对逆序对奇偶的影响，也是个经典问题。根据区间长度和循环移位次数的奇偶，实际上可以$O(1)$地确定对逆序对奇偶的影响，也就能确定操作后先手是否必胜。这里不会推，可以观察样例，也能得到区间长度和次数奇偶对逆序对的影响。

G

计算几何 交互

一个$n$个点的简单多边形，用不超过$n-2$次询问，确定这个多边形的面积。每次可以得到一个$x=C$的直线，在位于多边形边界上和内部的部分的长度

记我们询问得到的这个东西是个函数$f(x)$，那么我们要求的面积，实际上就是$f(x)$在下标范围的内的积分。

并且，多边形的$n$个点至多把$x$轴分成了$n-1$个区间，每个区间内，这个函数都是分段线性的。线性的，只要两个点就能解出函数表达式，就能计算积分。对于一个区间$[x_i,x_{i+1}]$，如果$x_i,x_{i+1}$上都只有一个点，我们直接询问$f(x_i),f(x_{i+1})$即可确定这一段上的解析式。如果某一个$x$上有不止一个点，在这里两段函数就不连续了，询问得到的可能上另一段区间的端点的函数值，不能用来计算这一段的表达式，那么需要在区间内部$(x_i,x_{i+1})$选一个点询问，显然这样询问次数也不会超的，因为这样一次询问能解决不止一个点。

M

缩点+$dfs$判非零环+拓扑排序

$m$个操作，每个都形如，对模$n$余数为$a$的元素，加$b$，每个询问给一个起始元素，问随意使用这些操作，能否到达无穷个元素。

显然这些操作构成了一个图。而这个问题等价于能否在图上无限移动，且元素值的序列是发散的。在图上无限移动，一般等价于进入一个环，这里要求元素值序列发散，则是还要求进入的环，边权和不为0，这样每转一圈，元素值就会$+\sum w_i$。

有多次询问，考虑预处理，反向连边，缩点，从$scc$对应点出发拓扑排序，就能记录每个元素出发，能否到达一个环。准确来说是对于模$n$的每个余数除法，能否进入一个环，回答询问时直接查表即可。

这里的$scc$还要求至少存在一个非零环，这看起来能转化为是否存在正环，负环，可以用$spfa$判负环，但太慢。实际上非零环，直接对$scc$进行$dfs$，设$dfs$起点为$x$，如果能访问到一个点$y$，有两个不同深度，那么$x\to y$存在两条边权和不同的路径，并且由于这是$scc$，一定也存在一条$y\to x$的路径，把他们组合起来，就形成了两个经过$x,y$的环，且环的边权和不同，那么这两个环的边权和肯定不全为$0$，也就至少存在一个非零环

所以我们先对每个$scc$进行上述$dfs$，只对于存在非零环的$scc$作为拓扑排序起点。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int in[N],dfn[N],co[N],low[N],s[N],ind[N],top,cnt,tot;
vector<pair<int,int>>a[N];
vector<int>b[N];
int vis[N],loop[N],d[N];
bool ok;
inline void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    s[++top]=x;
    ind[x]=1;
    for(auto &[v,w]:a[x]){
        if(!dfn[v]){
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(ind[v]){
            low[x]=min(low[x],low[v]);
        }
    }

    if(low[x]==dfn[x]){
        ++tot;
        while(1){
            int X=s[top--];
            co[X]=tot;
            ind[X]=0;
            if(!(x^X)){
                break;
            }
        }
    }
}
void dfs(int u,int color){
    vis[u]=1;
    for(auto &[v,w]:a[u]){
        if(co[v]!=color)continue;
        if(vis[v]){
            if(d[v]!=d[u]+w){
                ok=1;
            }
        }
        else{
            d[v]=d[u]+w;
            dfs(v,color);
        }
    }
}
void solve() {
    int n,m,Q;
    cin>>n>>m>>Q;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        u%=n;
        u=(u+n)%n;
        int nxt=(u+v)%n;
        nxt=(nxt+n)%n;
        a[nxt].push_back({u,v});
    }
    for(int i=0;i<n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    vector<vector<int>>scc(tot+1);
    for(int i=0;i<n;i++){
        scc[co[i]].push_back(i);
        for(auto &[v,w]:a[i]){
            if(co[i]^co[v]){
                b[co[i]].push_back(co[v]);
                in[co[v]]++;
            }
        }
    }
    for(int i=1;i<=tot;i++){
        int x=scc[i][0];
        ok=0;
        dfs(x,i);
        if(ok){
            loop[i]=1;
        }
    }

    queue<int>q;
    for(int i=1;i<=tot;i++){
        if(!in[i]){
            q.push(i);
        }
    }
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int v:b[u]){
            loop[v]|=loop[u];
            if(--in[v]==0){
                q.push(v);
            }
        }
    }
    while(Q--){
        int x;
        cin>>x;
        x=(x%n+n)%n;
        if(loop[co[x]]){
            cout<<"Yes\n";
        }
        else{
            cout<<"No\n";
        }
    }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T=1; 
    // cin >> T;
    while (T--) {
        solve();
    }
}