题意略。
离线处理，离散化。然后就是简单的线段树了。需要根据mod 5的值来维护。具体看代码了。
/* 线段树+离散化+离线处理*/#include#include #include #include using namespace std;typedef long long ll;#define N 100010ll sum[N<<2][5];int a[N], n, m, cnt[N<<2];struct node { char c; int x;} q[N];void Up(int rt) { cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1]; for (int i=0; i<5; i++) sum[rt][i] = sum[rt<<1][i] + sum[rt<<1|1][(i-cnt[rt<<1]%5+5)%5];}void add(int idx, int val, int l, int r, int rt) { if (l == r) { cnt[rt] = 1; sum[rt][1] = val; return ; } int mid = (l + r) >> 1; if (idx <= mid) add(idx, val, l, mid, rt<<1); else add(idx, val, mid+1, r, rt<<1|1); Up(rt);}void del(int idx, int l, int r, int rt) { if (l == r) { sum[rt][1] = cnt[rt] = 0; return ; } int mid = (l + r) >> 1; if (idx <= mid) del(idx, l, mid, rt<<1); else del(idx, mid+1, r, rt<<1|1); Up(rt);}int main() { char s[10]; while (scanf("%d", &n) == 1) { m = 0; for (int i=0; i