树状数组模拟_ABC340_E - Mancala 2

• 问题简述
• 思路分析
• 参考代码
• 做题反思

问题简述

原题参考：E - Mancala 2
初始给出长度为n、m的数组a、b，要求给出m次操作后的数组a，每一次的操作流程如下：

1. 设定变量c = 0；
2. 取出a[b[i]]中的数字
3. 保证手上有一个球的情况下进行以下操作：
   • c++
   • 向a[(b[i]+c)%n]中放1

可以看原题，原题有一个动画演示

思路分析

首先吐槽一手，发现做了这个题，我觉得我应该提高一下我的阅读理解能力，说实话，这个题目我当时看了很久，而且还读假了，稍后说。分析一下题目，大致就是一个模拟的过程，首先是取出一个位置的数字，做单点修改，然后开始向指定位置开始放数字，大致可以看作是一个区间修改的操作；第一次做的时候脑子一抽，想着只要输出最后的数组即可，所以想着直接用差分数组来做，写了一大半突然想起这个单点修改的事，更蠢的是，当时还想当然的把单点修改作为区间长为1的区间修改即可，等写完了，突然想起来，我在修改之前还要查，这下好了，直接tle，以后还是少偷懒。第二天起来补题，开始用树状数组写，第一遍写完之后结果样例都没过，当时就懵b了，开始调，发现动画里面拿的位置和我输出的不一样，更懵了，然后我就发现了，读错题了！！！，c每次都要重置（但是我得说一句，不重置的做法恶心一点），改了之后，样例倒是过了，交了一发，re！！！真是难绷，当时暂时也没看出来什么，以为是哪里的指针越界了，看了好久也没看出来，直到后面发现一个查询前缀和的变量可能爆了，但是爆了不应该是wa嘛，改了之后我也没报多大希望能ac，结果那13个re点过了，为什么爆数据是re[微笑]

参考代码

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 1e6+7;
ll n, m, a[N], b[N], pre = 0, tmp;
ll lowbit(ll x) {return x&-x;}
void change(ll i, ll x) {
    for(; i<=n; i+=lowbit(i)) a[i] += x;
} 
ll query(ll i) {
    ll res = 0;
    for(; i>0; i-=lowbit(i)) res += a[i];
    return res;
}
void solve() {
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        cin >> tmp;
        change(i, tmp-pre);
        pre = tmp;
    }
    for(int i=1; i<=m; i++) { 
        //说起来，这个b数组也不用记录，用个变量就行了
        cin >> b[i];
        ll hand = query(b[i]+1);
        //单点修改
        change(b[i]+1, -hand), change(b[i]+2, hand);
        int start = b[i] + 1 + 1;
        //这里是整体修改
        if(start > n) start %= n;
        if(!start) start = n;
        if(hand >= n) {
            change(1, hand/n);
            hand %= n;
        }
        //这里是分为是否会折返修改的讨论
        if(hand+start <= n+1) {
            change(start, 1), change(start+hand, -1);
        }
        else {
            change(start, 1);
            change(1, 1), change(hand+start-n, -1);
        }
    }
    for(int i=1; i<=n; i++) cout << query(i) << " \n"[i==n];
}
int main() {
#ifdef xrl
    freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
    FAST_IO;
    int t = 1;
    //cin >> t;
    while(t --) solve();
#ifdef xrl
    cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
    return 0;
}

做题反思

不得不说的必定是int牢底啊，又爆掉了，害我调了不少时间，苦思冥想一整天，不开longlong见祖宗；其次就是那个读错的c，我的语文水平已经到达这种地步了嘛，vocal，那这是真难绷