湖南建设监理官方网站,网站推广的基本方法为,广州免费核酸采集点时间,wordpress 二级域名附件传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个长度为nnn的数组aaa#xff0c;每次操作有两种#xff1a; (1)(1)(1) 给出x,yx,yx,y#xff0c;问aaa中下表在模xxx的时候#xff0c;模数等于yyy的位置aia_iai之和。 (2)(2)(2) 给出x,yx,yx,…传送门 文章目录题意思路题意
给你一个长度为nnn的数组aaa每次操作有两种
(1)(1)(1) 给出x,yx,yx,y问aaa中下表在模xxx的时候模数等于yyy的位置aia_iai之和。
(2)(2)(2) 给出x,yx,yx,y代表令axya_xyaxy。
思路
这个题的第一个询问就是从yyy下标开始让后每次递增xxx将经过的位置都算入答案这样的复杂度显然不能接受。
考虑每次递增的xxx如果我们能保证xnx\sqrt nxn那么递增的次数不会超过nnn\frac{n}{\sqrt n}\sqrt nnnn那么对于x≤nx\le \sqrt nx≤n的情况我们考虑预处理定义ans[x][y]ans[x][y]ans[x][y]表示在模数为xxx的情况下下标模xxx为yyy的答案这个显然可以nnn\sqrt nnn预处理。
考虑修改我们只需要枚举n\sqrt nn的模数让后将他们ansansans的值修改一下即可复杂度n\sqrt nn。
代码还是很好写的。
复杂度O(mn)O(m\sqrt n)O(mn)
// Problem: P3396 哈希冲突
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3396
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N150010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int val[N],block;
LL ans[600][600];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m); blocksqrt(n);for(int i1;in;i) scanf(%d,val[i]);for(int i1;in;i) {for(int j1;jblock;j) ans[j][i%j]val[i];}while(m--) {char op[2];int a,b;scanf(%s%d%d,op1,a,b);if(op[1]A) {if(ba) {puts(0);continue;}if(ablock) printf(%lld\n,ans[a][b]);else {LL ans0;for(int ib;in;ia) ansval[i];printf(%lld\n,ans);}} else {for(int i1;iblock;i) {ans[i][a%i]b-val[a];}val[a]b;}}return 0;
}
/**/
