链接：https://codeforces.com/contest/1921

$E-分类讨论-思路:$

$如果两个人之间 差值$$x$$为偶数，那么两人达到同一行那一步是由Alice迈出的。$

$注意到吃掉别人当且仅当你迈出一步，和他到同一行并且把他吃掉。$

$所以如果差值是偶数，要么Alice赢，要么平局。反之亦然。$

$算一下两人见面之前的y的范围，判一下进攻方$[$l_1$,$r_1$]$，防守方$[$l_2$,$r_2$]$，$

$是否满足$$l_1<=l_2+1$，$r_1>=r_2-1，$

$如果满足就肯定可以吃掉，否则平局。$

$然后特判一下两个人永远不会同一行的情况。$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#define IOS cin.tie(nullptr)->ios::sync_with_stdio(false);
#define endl '\n'
#define int long long

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 1000010,MOD = 998244353;
int h,w,xa,xb,ya,yb;
int T;
int ans;

void solve()
{
    cin>>h>>w>>xa>>ya>>xb>>yb;
    if(xa >= xb)
    {
        cout<<"Draw"<<endl;
        return;
    }
    int dist = xb - xa;
    int la = max(1ll,ya - dist/2), ra = min(w,ya + dist/2);
    if(dist & 1)
    {
        int lb = max(1ll,yb - dist/2), rb = min(w,yb + dist/2);
        if(la <= lb + 1 && ra >= rb - 1) cout<<"Alice"<<endl;
        else cout<<"Draw"<<endl;
    }else 
    {
        int lb = max(1ll,yb - (dist-1)/2), rb = min(w,yb + (dist-1)/2);
        if(lb <= la + 1 && rb >= ra - 1) cout<<"Bob"<<endl;
        else cout<<"Draw"<<endl;
    }
}
signed main(){
    IOS
    //T = 1;
    cin>>T;
    while(T -- )
    {
        solve();
    }
    return 0;
}

$F-根号分治+带权前缀和$

$题目分析：给定n个数，给定q个询问,每组询问包含s(起点),d(步长),k(个数),$

$求对应序列a_s+a_{s+d}⋅2+⋯+a_{s+d⋅(k−1)}⋅k之和,保证最后一项下标一定小于n$

$对于d=1的情况,所求序列和为连续子数组，可以用带权前缀和O(1)得到$

$带权子数组和[l,r):sum_{r}-sum_{l}-l⋅(a_{l}+a_{l+1}+···+a_{r-1})$

$即为sum_{r}-sum_{l}-l⋅(pre_r-pre_l)$

$对于d=2的情况$

$sum_0=0,sum_1=0;$

$sum_2=1⋅a_0,sum_3=1⋅a_1;$

$sum_4=1⋅a_0+2⋅a_2,sum_5=1⋅a_1+2⋅a_3$

$即sum_{i+2}=sum_i+(i/2+1)⋅a_i$

$令pre_{i+2}=pre_i+a_i$

$带权子数组和[l,r+2):即为sum_{r+2}-sum_{l}-(l/2)⋅(pre_{r+2}-pre_{l})$

$归纳得:元素和为sum_{r+d}-sum_{l}-(l/d)⋅(pre_{r+d}-pre_{l})$

$预处理要同时处理步长和前缀和,但是预处理全部步长会爆空间和时间$

$因此我们只处理小于\sqrt{n}的步长,这里直接取最大值320,预处理复杂度近似为O(nlogn)$

$对于步长大于等于\sqrt{n}的情况,直接暴力求，时间复杂度O(\sqrt{n})$

#include <bits/stdc++.h>
using namespace std;

const int MX_N = 100010, B = 320;
int64_t pre[B][MX_N+B], sum[B][MX_N+B];//一维步长,二维下标

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int64_t> a(n);
    for (auto &v: a) {
        cin >> v;
    }
    //预处理所有小于等于根号n的步长前缀和
    for (int d = 1; d < B; d++) {
        for (int i = 0; i < n; i++) {
            pre[d][i + d] = pre[d][i] + a[i];
            sum[d][i + d] = sum[d][i] + a[i] * (i / d + 1);
        }
    }

    while (q--) {
        int s, d, k;
        cin >> s >> d >> k;
        s--;
        //步长小于根号n
        if (d < B) {
            int r = s + d * k;
            cout << sum[d][r] - sum[d][s] - (pre[d][r] - pre[d][s]) * (s / d) << " ";
        } else {//步长大于等于根号n
            int64_t res = 0;
            for (int i = 0; i < k; i++) {
                res += a[s + d * i] * (i + 1);
            }
            cout << res << " ";
        }
    }
    cout << '\n';
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    for (cin >> T; T--;) {
        solve();
    }
    return 0;
}