魂逝_秦月歌 @ 2020-11-09 18:05:23
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cctype>
#include <algorithm>
#define _e putchar (' ')
#define _v putchar ('\n')
#define ll long long
#define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
inline int mx (int x,int y) {
return x>y?x:y;
}
inline int mn(int x,int y) {
return x<y?x:y;
}
inline void r(int &x) {
int s=0,w=1;
char ch=getchar ();
while (ch>'9'||ch<'0') {if(ch=='-') w=-1; ch=getchar ();}
while (ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+(ch^48); ch=getchar ();}
x=s*w;
}
inline void wr (int x) {
if(x<0) x=-x,putchar (45);
if(x<10) {
putchar (x+48);
return ;
}
wr(x/10);
putchar (x%10+48);
}
const int N=100005,mod=998244353;
int n,m,k,q,sum[N],id,a[N],b[N][5];
struct node {
int s,lazy;
}tree[N*4];
inline void pushup (int u) {
tree[u].s=tree[u<<1].s+tree[u<<1|1].s;
}
inline void build (int lt,int rt,int u) {
tree[u].lazy=1;
if(lt==rt) {
a[++id]=u;
r(tree[u].s);
}
int mid=(lt+rt)>>1;
build (lt,mid,u<<1);
build (mid+1,rt,u<<1|1);
}
inline void pushdown (int lt,int rt,int u) {
if(lt==rt||tree[u].lazy==1) return ;
tree[u<<1].lazy*=tree[u].lazy%mod;
tree[u<<1|1].lazy*=tree[u].lazy%mod;
int mid=(lt+rt)>>1;
tree[u<<1].s*=(mid-lt+1)*tree[u].lazy%mod;
tree[u<<1|1].s*=(rt-mid)*tree[u].lazy%mod;
tree[u].lazy=1;
}
inline void update (int nowl,int nowr,int delta,int tarl,int tarr,int u){
if(nowl>=tarl&&nowr<=tarr) {
tree[u].lazy*=delta%mod;
tree[u].s*=(nowr-nowl+1)*delta%mod;
return ;
}
pushdown (nowl,nowr,u);
int mid=(nowl+nowr)>>1;
if(nowl<=mid) update(nowl,mid,delta,tarl,tarr,u<<1);
if(nowr>mid) update(mid+1,nowr,delta,tarl,tarr,u<<1|1);
pushup(u);
}
inline void work(int q) {
if(b[q][1]==1){
a[b[q][2]]=(a[b[q][2]]+b[q][3])%mod;
return ;
}
if(b[q][1]==2) {
for(int j=1;j<=n;j++)
a[j]=(a[j]*b[q][2])%mod;
return ;
}
if(b[q][1]==3)
for(int i=3;i<=b[q][2]+2;i++)
work(b[q][i]);
}
int main () {
File("call");
r(n);
for(int i=1;i<=n;i++)
r(a[i]);
r(m);
for(int i=1;i<=m;i++) {
r(b[i][1]);
if(b[i][1]==1) r(b[i][2]),r(b[i][3]);
if(b[i][1]==2) r(b[i][2]);
if(b[i][1]==3) {
r(b[i][2]);
for(int j=1;j<=b[i][2];j++)
r(b[i][j+2]);
}
}
r(k);
for(int i=1;i<=k;i++) {
r(q);
work(q);
}
for(int i=1;i<n;i++)
wr(a[i]%mod),_e;
wr(a[n]);
_v;
return 0;
}by dead_X @ 2020-11-09 18:11:45
@魂逝_秦月歌 删掉fileIO部分，洛谷不支持文件IO
by 魂逝_秦月歌 @ 2020-11-09 18:13:41
@dead_X 我删了交上去错的呀。。。
by VOILinK @ 2020-11-14 09:10:23
我也是暴力爆零了呀
by 四旬老汉 @ 2020-11-15 01:31:02
暴力怎么会爆零呢，你们的暴力难道不是直接根据题意，遇上类型1就加一下，遇上类型2就遍历整个序列乘，遇上类型3就递归？ 请看真正的不动脑筋暴力：
#include <cstdio>
#include <vector>
#define MAX 100000
#define MOD 998244353
using namespace std;
//结构体存函数信息
struct fn{
//t是类型，1，2，3
//p对于1类函数，是执行加法的元素下标
//v对于1类函数，是增加的值，对于2类函数，是乘的值
int t, p, v;
} fs[MAX+1];
//第三种函数调用的函数编号
vector<int> subfs[MAX+1];
int n, m, Q, cs[MAX+1];//cs存放调用序列
long long a[MAX+1];//乘法会爆int，用long long
void calc(int call){//简单粗暴地计算结果
fn f = fs[call];
if (f.t == 1) {
a[f.p] = (a[f.p] + f.v) % MOD;
} else if (f.t == 2){
for(int i = 1; i <= n; i++){
a[i] = (a[i] * f.v) % MOD;
}
} else {
for(int i = 0; i < subfs[call].size(); i++){
calc(subfs[call][i]);
}
}
}
int main(){
// freopen("P7077_1.in", "r", stdin);
//freopen("call.in", "r", stdin);
//freopen("call.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%lld", &a[i]);
}
scanf("%d", &m);
for(int i = 1; i <= m; i++){
scanf("%d", &fs[i].t);
if (fs[i].t == 1) {
scanf("%d%d", &fs[i].p, &fs[i].v);
} else if (fs[i].t == 2){
scanf("%d", &fs[i].v);
} else {//t == 3
int c, cj;
scanf("%d", &c);
while(c--){
scanf("%d", &cj);
subfs[i].push_back(cj);
}
}
}
scanf("%d", &Q);
for(int i = 1; i <= Q; i++){
scanf("%d", &cs[i]);
}
for(int i = 1; i <= Q; i++){
calc(cs[i]);
}
for(int i = 1; i <= n; i++){
printf("%lld ", a[i]);
}
return 0;
}by lion0514 @ 2021-02-07 15:43:34
@四旬老汉 Orz