洛谷4月月赛R2
打酱油...
A.koishi的数学题
线性筛约数和就可以\(O(N)\)了...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;
typedef long long ll;
const int N=1e6+5;
inline ll read(){
char c=getchar(); ll x=0,f=1;
while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
return x*f;
}
bool notp[N]; int p[N/10], lp[N]; ll si[N];
void sieve(int n) {
si[1] = 1;
for(int i=2; i<=n; i++) {
if(!notp[i]) p[++p[0]] = i, lp[i] = i, si[i] = 1+i;
for(int j=1; j <= p[0] && i*p[j] <= n; j++) {
int t = i*p[j]; notp[t] = 1;
if(i % p[j] == 0) {
lp[t] = lp[i] * p[j];
if(lp[t] == t) si[t] = si[i] + lp[t];
else si[t] = si[t / lp[t]] * si[lp[t]];
break;
}
lp[t] = p[j];
si[t] = si[i] * (1 + p[j]);
}
}
for(int i=1; i<=n; i++) si[i] += si[i-1];
}
int n;
int main() {
n=read();
sieve(n);
for(int i=1; i<=n; i++) printf("%lld ", (ll) n * i - si[i]);
}
B：大爷的字符串题
卡读题...
容易发现就是求区间出现次数最多的权值
把区间众数的分块复制上T掉了，怒写莫队
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=2e5+5, mo = 998244353;
inline ll read(){
char c=getchar(); ll x=0,f=1;
while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
return x*f;
}
int n, Q, a[N], ans[N], mp[N], pos[N], block;
struct meow{
int l, r, id;
bool operator <(const meow &a) const {return pos[l] == pos[a.l] ? r < a.r : pos[l] < pos[a.l];}
} q[N];
int c[N], d[N], l, r, now;
inline void add(int x) {
d[c[x]]--; d[ ++c[x] ]++;
while(d[now+1]) now++;
}
inline void del(int x) {
d[c[x]]--; d[ --c[x] ]++;
while(!d[now]) now--;
}
void modui() {
l=1; r=0; d[0] = n;
sort(q+1, q+1+Q);
for(int i=1; i<=Q; i++) {
while(r < q[i].r) add(a[++r]);
while(r > q[i].r) del(a[r--]);
while(l < q[i].l) del(a[l++]);
while(l > q[i].l) add(a[--l]);
ans[ q[i].id ] = now;
}
}
int main() {
// freopen("in", "r", stdin);
n=read(); Q=read(); block = sqrt(n);
for(int i=1; i<=n; i++) mp[i] = a[i] = read(), pos[i] = (i-1)/block+1;
for(int i=1; i<=Q; i++) q[i].l = read(), q[i].r = read(), q[i].id = i;
sort(mp+1, mp+1+n); mp[0] = unique(mp+1, mp+1+n) - mp - 1;
for(int i=1; i<=n; i++) a[i] = lower_bound(mp+1, mp+1+mp[0], a[i]) - mp;
modui();
for(int i=1; i<=Q; i++) printf("%d\n", -ans[i]);
}
C：仓鼠的数学题
不会...我多项式除了算卷积什么都不会...
update:现在会了，在另一篇文章上
D：方方方的数据结构
题意：支持区间加，区间乘，单店询问，撤销某次操作
一眼感觉可以用线段树分治做，然后写写写，拍了几组数据不对啊...
然后调了两个小时，突然发现，因为有乘标记，每个操作不是独立的！，这还分治什么啊。
感觉其他的做法都很神奇
放一个错误的代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N=2e5+5, mo = 998244353;
inline ll read(){
char c=getchar(); ll x=0,f=1;
while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
return x*f;
}
int n, m, op, l, r, d, p, ans[N];
struct meow {
int op, l, r, d, s, t, id;
void print() {
printf("meow %d [%d, %d] %d [%d, %d]\n", op, l, r, d, s, t);
}
};
typedef vector<meow> vm;
vm a;
meow st[N]; int top;
inline void mod(ll &x) {if(x>=mo) x-=mo; else if(x<0) x+=mo;}
inline int Pow(ll a, int b) {
mod(a);
ll ans=1;
for(; b; b>>=1, a=a*a%mo)
if(b&1) ans=ans*a%mo;
return ans;
}
namespace seg {
#define mid ((l+r)>>1)
#define lc x<<1
#define rc x<<1|1
#define lson lc, l, mid
#define rson rc, mid+1, r
struct node{ ll val, a, b; node():b(1){} } t[N<<2];
inline void _add(int x, ll d) {
mod(t[x].a += d); mod(t[x].val += d);
}
inline void _mul(int x, ll d) {
t[x].a = (t[x].a * d) %mo;
t[x].b = (t[x].b * d) %mo;
t[x].val = (t[x].val * d) %mo;
}
inline void pushdn(int x) {
if(t[x].b != 1) {
_mul(lc, t[x].b);
_mul(rc, t[x].b);
t[x].b = 1;
}
if(t[x].a) {
_add(lc, t[x].a);
_add(rc, t[x].a);
t[x].a = 0;
}
}
void add(int x, int l, int r, int ql, int qr, ll d) {
if(ql<=l && r<=qr) _add(x, d);
else {
pushdn(x);
if(ql <= mid) add(lson, ql, qr, d);
if(mid < qr ) add(rson, ql, qr, d);
}
}
void mul(int x, int l, int r, int ql, int qr, ll d) {
if(ql<=l && r<=qr) _mul(x, d);
else {
pushdn(x);
if(ql <= mid) mul(lson, ql, qr, d);
if(mid < qr ) mul(rson, ql, qr, d);
}
}
int que(int x, int l, int r, int p) {
if(l == r) return t[x].val;
else {
pushdn(x);
if(p <= mid) return que(lson, p);
else return que(rson, p);
}
}
#undef mid
}
inline void add(int l, int r, int d) {
seg::add(1, 1, n, l, r, d);
}
inline void mul(int l, int r, int d) {
seg::mul(1, 1, n, l, r, d);
}
void recov(int bot) {
while(top != bot) {
meow &now = st[top--];
if(now.op == 1) add(now.l, now.r, -now.d);
if(now.op == 2) mul(now.l, now.r, Pow(now.d, mo-2));
}
}
int Q;
void cdq(int l, int r, vm &a) { if(l==1 && r==4) return;printf("\n-----------cdq [%d, %d]\n\n", l, r);
int mid = (l+r)>>1, bot = top;
vm b, c;
for(int i=0; i < (int)a.size(); i++) { //[s, t]
meow &now = a[i];
if(now.op == 4) continue;
printf("now %d [%d, %d]\n", now.id, now.s, now.t);
if(now.s == l && now.t == r) { puts("get");
if(now.op == 1) add(now.l, now.r, now.d);
if(now.op == 2) mul(now.l, now.r, now.d);
if(now.op == 3) ans[++Q] = seg::que(1, 1, n, now.l);
if(now.op <= 2) st[++top] = now;
}
else if(now.t <= mid) b.push_back(now);
else if(mid < now.s) c.push_back(now);
else {
meow q = now;
q.s = now.s; q.t = mid; b.push_back(q);
q.s = mid+1; q.t = now.t; c.push_back(q);
}
}
if(l != r) {
if(b.size()) cdq(l, mid, b);
if(c.size()) cdq(mid+1, r, c);
}
recov(bot);
}
int main() {
freopen("in", "r", stdin);
//freopen("a.out", "w", stdout);
n=read(); m=read();
for(int i=1; i<=m; i++) {
op=read();
if(op == 1) l=read(), r=read(), d=read(), a.push_back( (meow){op, l, r, d, i, -1, i} );
if(op == 2) l=read(), r=read(), d=read(), a.push_back( (meow){op, l, r, d, i, -1, i} );
if(op == 3) p=read(), a.push_back( (meow){op, p, 0, 0, i, i, i} );
if(op == 4) p=read()-1, a[p].t = i, a.push_back( (meow){4, 0, 0, 0, i, i, i} );
}
for(int i=0; i<m; i++) if(a[i].t == -1) a[i].t = m;
for(int i=0; i<m; i++) printf("%d ",i+1), a[i].print();
cdq(1, m, a);
for(int i=1; i<=Q; i++) {
if(ans[i] < 0) ans[i] += mo;
printf("%d\n", ans[i]);
}
//printf("\n\n%lld", ((ll)1e18 % mo + mo) %mo);
}