如何做网站方案,南宁建设职业技术网站,wordpress home.php,wordpress改写比赛链接
反思
A
为什么打表就我看不出规律#xff01;#xff01;#xff01; 定式思维太严重了T_T
B
纯智障分块题#xff0c;不知道为什么 B 100 B100 B100 比理论最优 B 300 B300 B300 更优#xff08;快了 3 倍#xff09;#xff0c;看来分块还是要学习一…比赛链接
反思
A
为什么打表就我看不出规律 定式思维太严重了T_T
B
纯智障分块题不知道为什么 B 100 B100 B100 比理论最优 B 300 B300 B300 更优快了 3 倍看来分块还是要学习一些卡常技巧的
C
菜死了不会
D
菜死了不会
题解
A
神奇的式子考虑打表 打表 可以发现一下两个规律
只有当 x y xy xy 是 2 2 2 的次幂时 f ( x , y ) f(x,y) f(x,y) 才可能不为 0 0 0 f ( x , y ) f ( x d , y d ) f(x,y)f(\frac{x}{d},\frac{y}{d}) f(x,y)f(dx,dy)其中 d gcd ( x , y ) d\gcd(x,y) dgcd(x,y) 且若 x y 2 k , x , y xy2^k,x,y xy2k,x,y 都为奇数且 ( x , y ) 1 (x,y)1 (x,y)1 时 f ( x , y ) k f(x,y)k f(x,y)k
考虑证明 考虑 x y xy xy 必须为偶数因为一直循环下去 x y xy xy 的值不变 f ( x , y ) f ( x d , y d ) f(x,y)f(\frac{x}{d},\frac{y}{d}) f(x,y)f(dx,dy) 是易得的 我们只需要考虑 x , y x,y x,y 都为奇数的情况因为 x , y x,y x,y 为偶数时 2 ∣ gcd ( x , y ) 2|\gcd(x,y) 2∣gcd(x,y) 令 x y xy xy则 f ( x , y ) f ( 2 y , x − y ) 1 f(x,y)f(2y,x-y)1 f(x,y)f(2y,x−y)1 因为 2 y , x − y 2y,x-y 2y,x−y 都为偶数所以 f ( x , y ) f ( y , x − y 2 ) 1 f(x,y)f(y,\frac{x-y}{2})1 f(x,y)f(y,2x−y)1 这样 x ′ y ′ xy x′y′ 的值就除了 2 2 2且因为 gcd ( x , y ) 1 \gcd(x,y)1 gcd(x,y)1所以 gcd ( y , x − y 2 ) 1 \gcd(y,\frac{x-y}{2})1 gcd(y,2x−y)1 所以 x y xy xy 只有当是 2 2 2 的次幂时 x ′ y ′ xy x′y′且操作次数为 l o g 2 ( x y ) log_2(xy) log2(xy)
我们发现这有值的点对个数是 O ( n l o g n ) O(nlogn) O(nlogn) 级别的 所以我们可以把所有有值的点对找出来然后询问就相当于二维数点了 离线询问 扫描线 树状数组即可 时间复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)
#include bits/stdc.h
#define pb push_back
#define lowbit(x) x-x
using namespace std;
typedef long long LL;
const int N300100,Q1000100;
struct Node{ int p1,p2,val;};
struct Node2{ int l,r,id,coef;};
int n,p[N],b[N];
LL tr[N],ans[Q];
Node used[N*40];
vectorNode2 query[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
bool cmp(const Node x,const Node y){ return x.p1y.p1;}
void add(int x,int v){ for(;xn;xlowbit(x)) tr[x]v;}
LL ask(int x){if(x0) return 0;LL res0;for(;x;x-lowbit(x)) restr[x];return res;
}
int main(){freopen(perm.in,r,stdin);freopen(perm.out,w,stdout);nread();for(int i1;in;i) p[i]read(),b[p[i]]i;int cnt0;for(int pw4,mi2;pwn1;pw1,mi)for(int x1;xpw;x2){int ypw-x;for(int k1;k*max(x,y)n;k) used[cnt]{b[x*k],b[y*k],mi};}int qread();for(int i1;iq;i){int lread(),rread();query[l-1].pb({l,r,i,-1}),query[r].pb({l,r,i,1});}sort(used1,usedcnt1,cmp);for(int i1,j0;in;i){while(jcntused[j1].p1i){j;assert(used[j].p21used[j].p2n);add(used[j].p2,used[j].val);}for(Node2 t:query[i]) ans[t.id]t.coef*(ask(t.r)-ask(t.l-1));}for(int i1;iq;i) printf(%lld\n,ans[i]/2);fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
B
不说了思想比较简单就是分块 块内用优先队列维护 时间复杂度 O ( n m l o g n ) O(n\sqrt mlogn) O(nm logn) m m m 为修改操作个数 块长设为 100 100 100 实测最优
#pragma GCC optimize(3)
#include bits/stdc.h
using namespace std;
const int N100100,MAXB1010,P1e97;
typedef pairint,int pii;
int n,m,a[N],pref[N],pos[N];
int B,sum[MAXB],tot[MAXB],tag[MAXB],_l[MAXB],_r[MAXB];
priority_queuepii,vectorpii,greaterpii pq[MAXB];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
inline int calc(int x){int cursqrt(x);return (pref[cur-1]1ll*(x-cur*cur1)*cur)%P;
}
inline void inc(int x,int y){ xy;if(xP) x-P;}
void rebuild(int Block){for(int i_l[Block];i_r[Block];i) a[i]tag[Block];tag[Block]tot[Block]sum[Block]0;while(!pq[Block].empty()) pq[Block].pop();for(int i_l[Block];i_r[Block];i){int sqsqrt(a[i]);inc(tot[Block],calc(a[i])),inc(sum[Block],sq);pq[Block].emplace(make_pair((sq1)*(sq1)-a[i],i));}assert(tot[Block]0);
}
void modify(int l,int r){if(pos[l]pos[r]){for(int il;ir;i) a[i];rebuild(pos[l]);return;}else{int il,jr;while(pos[i]pos[l]) a[i],i;while(pos[j]pos[r]) a[j],j--;rebuild(pos[l]),rebuild(pos[r]);for(int kpos[i];kpos[j];k){tag[k];pii tpq[k].top();while(t.firsttag[k]){pq[k].pop();inc(sum[k],1);int vsqrt(a[t.second]tag[k]);assert(v*va[t.second]tag[k]);pq[k].push(make_pair((v1)*(v1)-a[t.second],t.second));tpq[k].top();}inc(tot[k],sum[k]);}}
}
int query(int l,int r){int ans0;if(pos[l]pos[r]){rebuild(pos[l]);for(int il;ir;i) inc(ans,calc(a[i]));}else{rebuild(pos[l]),rebuild(pos[r]);int il,jr;while(pos[i]pos[l]) inc(ans,calc(a[i])),i;while(pos[j]pos[r]) inc(ans,calc(a[j])),j--;for(int kpos[i];kpos[j];k) inc(ans,tot[k]);}return ans;
}
int main(){freopen(play.in,r,stdin);freopen(play.out,w,stdout);for(int i1;i40000;i) pref[i](pref[i-1]((1ll*(i1)*(i1)-1ll*i*i)%PP)*i)%P;for(int i1;i40000;i) assert(pref[i]0);nread(),mread();for(int i1;in;i) a[i]read();B100;for(int i1;in;i) pos[i](i-1)/B1;for(int i1;ipos[n];i) _l[i]_r[i-1]1,_r[i]i*B;_r[pos[n]]n;for(int i1;ipos[n];i) rebuild(i);for(int i1;im;i){int opread(),lread(),rread();if(op1) modify(l,r);else printf(%d\n,query(l,r));}fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
C
感觉是到有点 nb 的题 不考虑翻转如何求 l i s lis lis 考虑枚举分界点 i i i那么答案 max { i 前面 0 的个数 i 后面 1 的个数 } \max\{i前面0的个数i后面1的个数\} max{i前面0的个数i后面1的个数} 这等价于 s 1 max i 1 n s u m i s1\max\limits_{i1}^{n} sum_i s1i1maxnsumi其中 s 1 s1 s1 为序列中 1 1 1 的个数 s u m i sum_i sumi 为把 0 0 0 的权值设为 1 1 1 1 1 1 的权值设为 − 1 -1 −1 的前缀和
考虑翻转操作 我们可以把这个问题等价地看成选出一段前缀和与 m m m 段不相交子区间不能与前缀相交的和的最大值 这一步感觉很难想也很难理解 具体我也不会证只能自己画图感性理解
然后就是经典的反悔贪心操作了找最大的区间然后区间取反用线段树维护即可 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
#include bits/stdc.h
#define int long long
using namespace std;
const int N200100;
int n,val[N],s[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
struct Node{int l,r,sum;int lmx,rmx,mx,Lp,Rp,LLp,RRp;int lmn,rmn,mn,Lq,Rq,LLq,RRq;bool tag;
}seg[N2];
Node operator (const Node lc,const Node rc){Node ret;ret.llc.l,ret.rrc.r,ret.tag0;ret.sumlc.sumrc.sum;ret.lmxlc.lmx,ret.LLplc.LLp;if(lc.sumrc.lmxret.lmx) ret.lmxlc.sumrc.lmx,ret.LLprc.LLp;ret.rmxrc.rmx,ret.RRprc.RRp;if(rc.sumlc.rmxret.rmx) ret.rmxrc.sumlc.rmx,ret.RRplc.RRp;ret.mxlc.rmxrc.lmx,ret.Lplc.RRp,ret.Rprc.LLp;if(lc.mxret.mx) ret.mxlc.mx,ret.Lplc.Lp,ret.Rplc.Rp;if(rc.mxret.mx) ret.mxrc.mx,ret.Lprc.Lp,ret.Rprc.Rp;ret.lmnlc.lmn,ret.LLqlc.LLq;if(lc.sumrc.lmnret.lmn) ret.lmnlc.sumrc.lmn,ret.LLqrc.LLq;ret.rmnrc.rmn,ret.RRqrc.RRq;if(rc.sumlc.rmnret.rmn) ret.rmnrc.sumlc.rmn,ret.RRqlc.RRq;ret.mnlc.rmnrc.lmn,ret.Lqlc.RRq,ret.Rqrc.LLq;if(lc.mnret.mn) ret.mnlc.mn,ret.Lqlc.Lq,ret.Rqlc.Rq;if(rc.mnret.mn) ret.mnrc.mn,ret.Lqrc.Lq,ret.Rqrc.Rq;return ret;
}
void down(int x){swap(seg[x].lmx,seg[x].lmn),swap(seg[x].rmx,seg[x].rmn),swap(seg[x].mx,seg[x].mn);swap(seg[x].Lp,seg[x].Lq),swap(seg[x].Rp,seg[x].Rq),swap(seg[x].LLp,seg[x].LLq),swap(seg[x].RRp,seg[x].RRq);seg[x].sum*-1,seg[x].lmx*-1,seg[x].rmx*-1,seg[x].mx*-1,seg[x].lmn*-1,seg[x].rmn*-1,seg[x].mn*-1;seg[x].tag^1;
}
void pushdown(int x){if(seg[x].tag) down(x1),down(x1^1);seg[x].tag0;
}
void build(int l,int r,int x){if(lr){ seg[x]{l,l,val[l],val[l],val[l],val[l],l,l,l,l,val[l],val[l],val[l],l,l,l,l,0};return;}int mid(lr)1; build(l,mid,x1),build(mid1,r,x1^1);seg[x]seg[x1]seg[x1^1];
}
void modify(int l,int r,int x,int L,int R){if(LlrR){ down(x);return;}pushdown(x);int mid(lr)1;if(midL) modify(l,mid,x1,L,R);if(midR) modify(mid1,r,x1^1,L,R);seg[x]seg[x1]seg[x1^1];
}
signed main(){freopen(lis.in,r,stdin);freopen(lis.out,w,stdout);nread();int ans0;for(int i1;in;i){int aread(),bread();if(a0) a1;else a-1,ansb;val[i]a*b,s[i]s[i-1]val[i];}int mx0;s[0]-1e18;for(int i1;in;i) if(s[i]s[mx]) mxi;build(1,n,1);if(s[mx]0) anss[mx],modify(1,n,1,1,mx);printf(%lld\n,ans);int mread();for(int i1;im;i){Node retseg[1];if(ret.mx0) ansret.mx,modify(1,n,1,ret.Lp,ret.Rp);printf(%lld\n,ans);}fprintf(stderr,%d ms\n,int64_t(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
D
考虑暴力是 f i , j f_{i,j} fi,j 表示当前在 i i i前一个选 j j j 的最大长度因为 p i ≠ k p_i\neq k pik 的限制很松所以直接记录最大值和次大值就可以维护时间复杂度 O ( n 3 ) O(n^3) O(n3)
于是我们可以猜测需要保留的转移状态不会太多事实上是真的 我们令三元组 ( l e n t h , p r e , i ) (lenth,pre,i) (lenth,pre,i) 表示当前在 i i i上一个在 p r e pre pre长度为 l e n t h lenth lenth 的状态 我们考虑用这个东西转移 每次答案我们需要把 a j a i a_ja_i ajai 的 ( l e n t h , p r e , j ) (lenth,pre,j) (lenth,pre,j) 取出然后更新 i i i 的状态 结论1对于 i i i 只需要保留 l e n t h lenth lenth 最长的两个且满足 j p ≠ j q j_p\neq j_q jpjq 的状态 首先 j j j 相等的状态只需要保留一个那么后面最多只会排除掉 1 1 1 个状态所以只需要暴力 2 2 2 个状态 结论2只需要取出 ( l e n t h , p r e , j ) (lenth,pre,j) (lenth,pre,j) 的前 5 5 5 大 l e n t h lenth lenth且对于 p r e pre pre 相同的我们只保留最大的 2 2 2 个 为什么考虑如果前两个的 p r e pre pre 都和 i i i 一样那么后两个必然有两个 p r e pre pre 不相同的是可以更新出 2 2 2 个有效答案的
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)但常数有点大我稍微卡了一下常
#pragma GCC optimize(3)
#include bits/stdc.h
#define pb push_back
#define lowbit(x) x-x
using namespace std;
const int N200100;
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
struct Node{ int lenth,pre,x;//以x结尾的长度为lenth的序列前一个为pre的一种转移
};
vectorNode tr[N];
int n,a[N],p[N],cnt[N];
bool cmp(const Node o1,const Node o2){ return o1.lentho2.lenth;}
auto select(vectorNode vec){sort(vec.begin(),vec.end(),cmp);vectorNode ret;for(auto t:vec){int c0;for(auto q:ret) if(q.pret.pre) c;if(c2) continue;ret.pb(t);if(ret.size()5) break;}return ret;
}
const int B20;
void add(int x,vectorNode ad){for(;xn;xlowbit(x)){for(auto t:ad) tr[x].pb(t);if(tr[x].size()B) tr[x]select(tr[x]);}
}
auto query(int x){vectorNode ret;for(;x;x-lowbit(x)) for(auto t:tr[x]) ret.pb(t);return ret;
}
void work(){nread();for(int i1;in;i) a[i]read();for(int i1;in;i) p[i]read();int ans0;for(int i1;in;i){auto retquery(a[i]-1);ret.pb({0,-1,-1});//以i为开头retselect(ret);vectorNode cur;for(auto t:ret)if(p[i]!t.pre)if(!cur.size()||t.x!cur.back().pre){cur.pb({t.lenth1,t.x,i});if(cur.size()2) break;}for(auto t:cur) ansmax(ans,t.lenth);add(a[i],cur);}printf(%d\n,ans);for(int i1;in;i) tr[i].clear();
}
int main(){freopen(cactus.in,r,stdin);freopen(cactus.out,w,stdout);int Tread();while(T--) work();fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
