zufe 2485 Sequence

zufe 2485 Sequence"/>

zufe 2485 Sequence

题目描述

有一个序列，n个非负整数，a1，a2，a3，a4......，an

有Q次操作，

操作分两种：

1 p x：将a[p]改为x

2 L R：查询区间[L,R]中 大于等于pow(17，last%5) 的数字有几个，last是上一次询问的答案，一开始设last为0。

输入

第一行输入T，表示有T组测试数据

每组测试数据，

第一行输入n，

第二行输入n个非负整数

第三行输入Q，

接下来Q行每行输入一种操作

1<=n<=100000

1<=Q<=100000

a[i] 非负整数，（<= 10000000）

输出

每次询问，输出答案。

样例输入

1
5
213 43 217 78 982
5
1 3 45
2 1 4
2 3 5
1 5 678
2 1 5 

样例输出

4
0

5

题解：
因为last%5,因此只需记录5个值即可。#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int a[maxn],k[5];
struct node
{int left,right,mid;int num[5];
}tree[maxn<<2];
void push_up(int rt)
{for(int i=0;i<5;i++)tree[rt].num[i]=tree[rt<<1].num[i]+tree[rt<<1|1].num[i];
}
void build(int l,int r,int rt)
{tree[rt].left=l;tree[rt].right=r;tree[rt].mid=(l+r)/2;if(l==r){for(int i=0;i<5;i++){if(a[l]>=k[i])tree[rt].num[i]=1;elsetree[rt].num[i]=0;}return;}build(l,tree[rt].mid,rt<<1);build(tree[rt].mid+1,r,rt<<1|1);push_up(rt);
}
void update(int L,int x,int rt)
{if(tree[rt].left==tree[rt].right){for(int i=0;i<5;i++){if(x>=k[i])tree[rt].num[i]=1;elsetree[rt].num[i]=0;}return;}if(L<=tree[rt].mid)update(L,x,rt<<1);elseupdate(L,x,rt<<1|1);push_up(rt);
}
int query(int l,int r,int rt,int t)
{if(tree[rt].left>=l&&tree[rt].right<=r){return tree[rt].num[t];}int ans=0;if(tree[rt].mid>=l)ans+=query(l,r,rt<<1,t);if(tree[rt].mid<r)ans+=query(l,r,rt<<1|1,t);return ans;
}
int main()
{k[0]=1;for(int i=1;i<5;i++)k[i]=k[i-1]*17;int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,n,1);int Q;scanf("%d",&Q);int last=0;while(Q--){int op,l,r;scanf("%d%d%d",&op,&l,&r);if(op==1) update(l,r,1);else{last=query(l,r,1,last%5);printf("%d\n",last);}}}return 0;
}