【LOJ】#2028. 「SHOI2016」随机序列

题解

我们发现只有从第一个往后数，用乘号联通的块是有贡献的

为什么，因为后面所有表达式肯定会有 + ，还会有个-，贡献全都被抵消了

所以我们处理出前缀乘积，然后乘上表达式的方案数

答案就是\(\sum_{i = 1}^{n - 1} S[i] * 2 * 3^{n - 1 - i} + S[n]\)

设新值为v，旧值为u，修改的时候相当于一段区间乘上\(\frac{v}{u}\)

线段树维护即可

代码

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <vector>

#include <set>

#include <cmath>

#include <bitset>

#define enter putchar('\n')

#define space putchar(' ')

//#define ivorysi

#define pb push_back

#define MAXN 100005

#define mo 974711

#define pii pair<int,int>

#define mp make_pair

#define fi first

#define se second

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 - '0' + c;

	c = getchar();

    }

    res = res * f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) out(x / 10);

    putchar('0' + x % 10);

}

const int MOD = 1000000007;

int N,Q;

int a[MAXN],pow3[MAXN],Line[MAXN];

struct node {

    int l,r,sum,MK;

}tr[MAXN * 4];

int mul(int a,int b) {

    return 1LL * a * b % MOD;

}

int inc(int a,int b) {

    return a + b >= MOD ? a + b - MOD : a + b;

}

int fpow(int x,int c) {

    int res = 1,t = x;

    while(c) {

	if(c & 1) res = mul(res,t);

	t = mul(t,t);

	c >>= 1;

    }

    return res;

}

void update(int u) {

    tr[u].sum = inc(tr[u << 1].sum,tr[u << 1 | 1].sum);

}

void addlazy(int u,int v) {

    tr[u].sum = mul(tr[u].sum,v);

    tr[u].MK = mul(tr[u].MK,v);

}

void pushdown(int u) {

    if(tr[u].MK != 1) {

	addlazy(u << 1,tr[u].MK);

	addlazy(u << 1 | 1,tr[u].MK);

	tr[u].MK = 1;

    }

}

void build(int u,int L,int R) {

    tr[u].l = L;tr[u].r = R;

    tr[u].MK = 1;

    if(L == R) {

	tr[u].sum = Line[L];

	return ;

    }

    int mid = (L + R) >> 1;

    build(u << 1,L,mid);

    build(u << 1 | 1,mid + 1,R);

    update(u);

}

void Change(int u,int L,int R,int v) {

    if(tr[u].l == L && tr[u].r == R) {

	addlazy(u,v);return;

    }

    int mid = (tr[u].l + tr[u].r) >> 1;

    pushdown(u);

    if(R <= mid) Change(u << 1,L,R,v);

    else if(L > mid) Change(u << 1 | 1,L,R,v);

    else Change(u << 1,L,mid,v),Change(u << 1 | 1,mid + 1,R,v);

    update(u);

}

void Solve() {

    read(N);read(Q);

    for(int i = 1 ; i <= N ; ++i) read(a[i]);

    pow3[0] = 1;

    for(int i = 1 ; i <= N ; ++i) pow3[i] = mul(pow3[i - 1],3);

    int t = 1;

    for(int i = 1 ; i <= N ; ++i) {

	t = mul(t,a[i]);

	if(i != N) Line[i] = mul(t,mul(2,pow3[N - i - 1]));

	else Line[i] = t;

    }

    build(1,1,N);

    int u,v;

    while(Q--) {

	read(u);read(v);

	t = mul(v,fpow(a[u],MOD - 2));a[u] = v;

	Change(1,u,N,t);

	out(tr[1].sum);enter;

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

番外：童年的回忆

（话说我要不要把另一个blog上童年的回忆的三道题搬过来呢？

当年，是我第一次考省选（是，我初二）

我当时很天真的以为LN妹子那么少没准我真能考进省队呢

怀着这种天真的想法进了省选的考场，看完之后……发现三道题都不会，连煞笔暴力都不会

我尝试用我上个月刚学的lca去写某个最裸的暴力，不知道多少分，好吧，五个小时里我有三个小时都在debug 倍增lca（菜成狗了呀><

后来我第一天爆零了，第二天继续懵逼er

发现有提答，我很开心的用我NOIP前刚学的dfs写了一个大搜索！很高兴的连最小的点也跑不出来（手动再见

然后发现有两个点性质非常特殊啊，手玩了一下

哎我最后这场省选有分啊，好像第二天有道写了暴力，然后还有提答有20，一共有40分呢！

LN队线（好吧，当年卡线进省队的是24><)也就80几分的样子，看来我努努力还是可以进省队的（当年LN的女队是谁啊？忘记了。。。NEYC的？

在幼小的心灵里从此觉得省选是个非常毒瘤的东西，最多也就打打暴力了呀。。暴力打好了没准就进了

现在我忽然发现……哎学长为啥当年拿的分那么少感觉这场比赛并没有那么难啊……

后来初三全省就我一个妹子NOIP一等，LN又规定只有NOIP一等奖选手才能选省队，考完NOIP直接钦定省队了啊，美滋滋（然鹅我并没有重视这场NOI……因为我要中考QAQ

虽然最后考了全省第8，然而省队名额只有7个，其实也是没过省队线的qwq，看着学长们明明很靠前却被1/3卡掉，难过

算了，再多的事等到之后再回忆吧，我写的太多了。。。

巴特西

【LOJ】#2028. 「SHOI2016」随机序列

题解

代码

番外：童年的回忆

最新文章

热门文章