<span>2018 ACMICPC上海大都会赛重现赛 H - A Simple Problem with Integers (线段树，循环节)</span>
2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 H - A Simple Problem with Integers (线段树，循环节)
链接：https://ac.nowcoder.com/acm/contest/163/H
来源：牛客网
链接：https://ac.nowcoder.com/acm/contest/163/H来源：牛客网
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
You have N integers A1, A2, ... , AN. You are asked to write a program to receive and execute two kinds of instructions:
\1. C a b means performing Ai = (Ai2 mod 2018) for all Ai such that a ≤ i ≤ b.
\2. Q a b means query the sum of Aa, Aa+1, ..., Ab. Note that the sum is not taken modulo 2018.
输入描述:
The first line of the input is T(1≤ T ≤ 20), which stands for the number of test cases you need to solve.The first line of each test case contains N (1 ≤ N ≤ 50000).The second line contains N numbers, the initial values of A1, A2, ..., An. 0 ≤ Ai < 2018. The third line contains the number of operations Q (0 ≤ Q ≤ 50000). The following Q lines represents an operation having the format "C a b" or "Q a b", which has been described above. 1 ≤ a ≤ b ≤ N.
输出描述:
For each test case, print a line "Case #t:" (without quotes, t means the index of the test case) at the beginning.You need to answer all Q commands in order. One answer in a line.
示例1
输入
[复制](javascript:void(0)😉
1
8
17 239 17 239 50 234 478 43
10
Q 2 6
C 2 7
C 3 4
Q 4 7
C 5 8
Q 6 7
C 1 8
Q 2 5
Q 3 4
Q 1 8
输出
[复制](javascript:void(0)😉
Case #1:
779
2507
952
6749
3486
9937
题意：
给你一个含有n个数的数组，
然后Q个操作，
操作有2种类型:
- 1 给你一个区间\([l,r]\) ，把所有\(l<=i<=r\) 的a[i] 变为 \(a[i]*a[i] mod 2018\)
- 2 给你一个区间\([l,r]\) ，把所有\(l<=i<=r\) 的a[i]的sum和（不对2018取模）
思路：
我们知道一个数一直平方同时对一个数取模，是一定有一个循环周期的。
而对于2018这个数，我们可以通过暴力来计算对他取模的循环周期。
每个元素平方最大周期为6，且6是其他所有周期的公倍数。
我们可以在每个节点维护一个大小为6的数组，同时维护一个代表从数组中取哪个元素的指针。
因为有的数在进入循环节前需要经过几次修改，打表发现进入循环节前的修改次数都不超过5，
所以可以在前五次暴力更新节点，之后才开始利用线段树的lazy标记。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline void getInt(int* p);
const int maxn = 100000 + 10;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
const ll mod = 2018ll;
struct node
{
int p;
int cnt;
int val[7];
int l, r;
int laze;
} segment_tree[maxn << 2];
int T;
int n;
void pushup(int rt)
{
segment_tree[rt].cnt = min(segment_tree[rt << 1].cnt, segment_tree[rt << 1 | 1].cnt);
if (segment_tree[rt].cnt >= 5)
{
segment_tree[rt].p = 0;
repd(i, 0, 5)
{
segment_tree[rt].val[i] = segment_tree[rt << 1].val[(segment_tree[rt << 1].p + i) % 6] + segment_tree[rt << 1 | 1].val[(segment_tree[rt << 1 | 1].p + i) % 6];
}
} else
{
segment_tree[rt].val[0] = segment_tree[rt << 1].val[segment_tree[rt << 1].p] + segment_tree[rt << 1 | 1].val[segment_tree[rt << 1 | 1].p];
}
}
void build(int rt, int l, int r)
{
segment_tree[rt].l = l;
segment_tree[rt].r = r;
segment_tree[rt].p = 0;
segment_tree[rt].cnt = 0;
segment_tree[rt].laze = 0;
if (l == r)
{
scanf("%d", &segment_tree[rt].val[0]);
} else
{
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
// segment_tree[rt].val[0] = segment_tree[rt << 1].val[0] + segment_tree[rt << 1 | 1].val[0];
pushup(rt);
}
}
void pushdown(int rt)
{
segment_tree[rt << 1 | 1].p = (segment_tree[rt << 1 | 1].p + segment_tree[rt].laze) % 6;
segment_tree[rt << 1 | 1].laze += segment_tree[rt].laze;
segment_tree[rt << 1 ].p = (segment_tree[rt << 1 ].p + segment_tree[rt].laze) % 6;
segment_tree[rt << 1 ].laze += segment_tree[rt].laze;
segment_tree[rt].laze = 0;
}
void update(int rt, int l, int r)
{
if (segment_tree[rt].l == segment_tree[rt].r) {
segment_tree[rt].cnt++;
if (segment_tree[rt].cnt < 5)
{
segment_tree[rt].val[0] = segment_tree[rt].val[0] * segment_tree[rt].val[0] % mod;
} else if (segment_tree[rt].cnt == 5)
{
segment_tree[rt].p = 0;
segment_tree[rt].val[0] = segment_tree[rt].val[0] * segment_tree[rt].val[0] % mod;
for (int i = 1; i <= 5; ++i)
{
segment_tree[rt].val[i] = segment_tree[rt].val[i - 1] * segment_tree[rt].val[i - 1] % mod;
}
} else
{
segment_tree[rt].p = (segment_tree[rt].p + 1) % 6;
}
return;
}
if (segment_tree[rt].laze)
{
pushdown(rt);
}
if (segment_tree[rt].l >= l && segment_tree[rt].r <= r)
{
if (segment_tree[rt].cnt >= 5)
{
segment_tree[rt].laze++;
segment_tree[rt].p = (segment_tree[rt].p + 1) % 6;
} else
{
int mid = (segment_tree[rt].l + segment_tree[rt].r) >> 1;
update(rt << 1, l, r);
update(rt << 1 | 1, l, r);
pushup(rt);
}
return;
}
int mid = (segment_tree[rt].l + segment_tree[rt].r) >> 1;
if (r > mid)
update(rt << 1 | 1, l, r);
if (l <= mid)
update(rt << 1, l, r);
pushup(rt);
}
int query(int rt, int l, int r)
{
if (segment_tree[rt].l != segment_tree[rt].r && segment_tree[rt].laze)
pushdown(rt);
if (segment_tree[rt].l >= l && segment_tree[rt].r <= r)
{
return segment_tree[rt].val[segment_tree[rt].p % 6];
} else
{
int res = 0;
int mid = (segment_tree[rt].l + segment_tree[rt].r) >> 1;
if (r > mid)
res += query(rt << 1 | 1, l, r);
if (l <= mid)
{
res += query(rt << 1, l, r);
}
return res;
}
}
int main()
{
//freopen("D:\\code\\text\\input.txt","r",stdin);
//freopen("D:\\code\\text\\output.txt","w",stdout);
scanf("%d", &T);
for (int cas = 1; cas <= T; ++cas)
{
printf("Case #%d:\n", cas );
scanf("%d", &n);
build(1, 1, n);
int m;
scanf("%d", &m);
char str[3];
int l, r;
while (m--)
{
scanf("%s %d %d", str, &l, &r);
if (str[0] == 'Q')
{
printf("%d\n", query(1, l, r) );
} else
{
update(1, l, r);
}
}
}
return 0;
}
inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
}
else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}
查看23道真题和解析
别扯什么自己这那的 我感觉领导确实已经给你很多时间和空间了 自己还是想想有没有真的用心去做 不是什么东西都要别人推着你去干的 总得学会主动一点吧 最后中肯地说一句 卷不了还是别走互联网这条路了 不好意思说话有些直白但希望你可以明白我的意思