社区讨论
我这个缺省源还能加啥算法呢qwq
学术版参与者 15已保存回复 23
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 23 条
- 当前快照
- 1 份
- 快照标识符
- @mju4svr2
- 此快照首次捕获于
- 2025/12/31 22:48 2 个月前
- 此快照最后确认于
- 2026/01/03 10:55 2 个月前
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int mod=1e9+7;
int n,m;
void Max(int &a,int b){a>=b?0:a=b;}
void Min(int &a,int b){a<=b?0:a=b;}
int lowbit(int x){return x&(-x);}
int qpow(int a,int b){
int ans=1;
while(b>0){
if(b&1){
ans*=a;
ans%=mod;
}
a*=a;
a%=mod;
b/=2;
}
return ans;
}
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)write(x/10);
putchar(x%10+'0');
return;
}
namespace seg_tree{
int w[N];
struct TreeNode{
int l,r;
int sum;
int tag;
}t[N<<2];
// TreeNode operator + (TreeNode &A,TreeNode &B){
// TreeNode C;
// C.l=A.l;
// C.r=B.r;
// C.sum=A.sum+B.sum;
// return C;
// }
void pushup(int rt){
t[rt].sum=t[(rt<<1)].sum+t[(rt<<1)+1].sum;
return;
}
void build(int rt,int l,int r){
t[rt].l=l,t[rt].r=r;
t[rt].tag=0;
if(l==r){
t[rt].sum=w[l];
return;
}
int mid=(l+r)/2;
build((rt<<1),l,mid);
build((rt<<1)+1,mid+1,r);
pushup(rt);
return;
}
void modify(int rt,int v){
t[rt].tag+=v;
t[rt].sum+=v*(t[rt].r-t[rt].l+1);
return;
}
void pushdown(int rt){
modify(rt<<1,t[rt].tag);
modify((rt<<1)+1,t[rt].tag);
t[rt].tag=0;
return;
}
void update(int rt,int l,int r,int v){
if(l<=t[rt].l && t[rt].r<=r){
modify(rt,v);
return;
}
pushdown(rt);
int mid=(t[rt].l+t[rt].r)/2;
if(l<=mid)update((rt<<1),l,r,v);
if(r>mid)update((rt<<1)+1,l,r,v);
pushup(rt);
return;
}
int query(int rt,int l,int r){
if(l<=t[rt].l && t[rt].r<=r){
return t[rt].sum;
}
pushdown(rt);
int mid=(t[rt].l+t[rt].r)/2;
int cnt=0;
if(l<=mid)cnt+=query(rt<<1,l,r);
if(r>mid)cnt+=query((rt<<1)+1,l,r);
return cnt;
}
}
namespace dij_sp{
struct EdgeNode{
int v;
int w;
};
bool operator < (const EdgeNode &A,const EdgeNode &B){
return A.w<B.w;
}
priority_queue<EdgeNode>q;
vector<EdgeNode>e[N];
int dis[N];
void init(int s){
for(int i=0;i<N;i++)dis[i]=LLONG_MAX;
dis[s]=0;
}
void dijstra(int s){
q.push({s,0});
while(!q.empty()){
int id=(q.top()).v;
int w=(q.top()).w;
q.pop();
if(w>dis[id])continue;
for(EdgeNode to:e[id]){
int cost=w+to.w;
if(cost<dis[to.v]){
dis[to.v]=cost;
q.push({to.v,cost});
}
}
}
return;
}
}
namespace fa_sp{
struct EdgeNode{
int v;
int w;
};
queue<int>q;
vector<EdgeNode>e[N];
int dis[N],len[N],in[N];
void init(int s){
for(int i=1;i<N;i++)dis[i]=LLONG_MAX;
for(int i=1;i<N;i++)len[i]=0;
for(int i=1;i<N;i++)in[i]=0;
for(int i=1;i<N;i++)e[i].clear();
while(!q.empty())q.pop();
dis[s]=0;
in[s]=1;
return;
}
bool spfa(int s){
q.push(s);
while(!q.empty()){
int id=q.front();
q.pop();
in[id]=0;
if(len[id]>n)return 1;
for(EdgeNode to:e[id]){
int cost=dis[id]+to.w;
if(cost>=dis[to.v])continue;
len[to.v]=len[id]+1;
dis[to.v]=cost;
if(!in[to.v]){
in[to.v]=1;
q.push(to.v);
}
}
}
return 0;
}
}
//namespace flo_sp{
// int dis[N][N];
// void init(){
// for(int i=0;i<N;i++){
// for(int j=0;j<N;j++){
// dis[i][j]=1e18;
// }
// }
// for(int i=0;i<N;i++)dis[i][i]=0;
// }
// void Floyd(){
// for(int k=1;k<=n;k++){
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// Min(dis[i][j],dis[i][k]+dis[k][j]);
// }
// }
// }
// return;
// }
//}
namespace fen_tree{
int t[N<<1];
void update(int rt,int v){
for(int i=rt;i<N;i+=lowbit(i)){
t[i]+=v;
}
return;
}
int query(int rt){
int ans=0;
for(int i=rt;i>=1;i-=lowbit(i)){
ans+=t[i];
}
return ans;
}
}
namespace lca{
int st[21][N];
int deep[N];
vector<int>e[N];
void dfs(int id,int fa){
st[0][id]=fa;
deep[id]=deep[fa]+1;
for(int i=1;i<=20;i++){
st[i][id]=st[i-1][st[i-1][id]];
}
for(int to:e[id]){
if(to==fa)continue;
dfs(to,id);
}
return;
}
int lca(int a,int b){
if(deep[a]<deep[b])swap(a,b);
int diff=deep[a]-deep[b];
for(int i=20;i>=0;i--){
if(diff&(1<<i)){
a=st[i][a];
}
}
if(a==b)return a;
for(int i=20;i>=0;i--){
if(st[i][a]!=st[i][b]){
a=st[i][a];
b=st[i][b];
}
}
a=st[0][a];
return a;
}
}
namespace st{
int a[N];
int st[21][N];
void init(){
for(int i=1;i<=n;i++)st[0][i]=a[i];
for(int i=1;i<=20;i++){
for(int j=1;j<=n-(1<<i)+1;j++){
st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
}
return;
}
int query(int l,int r){
int diff=r-l+1;
int lg=log2(diff);
return max(st[lg][l],st[lg][r-(1<<lg)+1]);
}
}
namespace dsu{
int fa[N];
void init(){
for(int i=0;i<N;i++)fa[i]=i;
return;
}
int find(int id){
return id==fa[id]?id:fa[id]=find(fa[id]);
}
}
namespace mst{
struct EdgeNode{
int u,v,w;
};
EdgeNode e[N];
vector<EdgeNode>v;
int ans=0;
int cnt=0;
void init(){
ans=0;
cnt=0;
dsu::init();
}
bool cmp(EdgeNode A,EdgeNode B){
return A.w<B.w;
}
int mst(){
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++){
int fu=dsu::find(e[i].u);
int fv=dsu::find(e[i].v);
if(fu!=fv){
dsu::fa[fu]=fv;
v.push_back({e[i].u,e[i].v,e[i].w});
ans+=e[i].w;
cnt++;
}
}
return ans;
}
}
namespace exgcd{
void exgcd(int a,int b,int &x, int &y) {
if(!b){
x=1;
y=0;
} else {
exgcd(b,a%b,y,x);
y-=a/b*x;
}
}
int inv(int a,int m) {
int x,y;
exgcd(a,m,x,y);
return ((x%m)+m)%m;
}
}
namespace lininv{
int inv[N];
void init(){
inv[1]=1;
for (int i=2;i<=n;i++) {
inv[i]=(mod-mod/i)*inv[mod%i];
inv[i]%=mod;
}
return;
}
}
namespace linsieve{
bool notprime[N];
vector<int>pri;
void pre(){
notprime[1]=1;
for (int i = 2; i <= n; ++i) {
if (!notprime[i]) {
pri.push_back(i);
}
for (int prij:pri) {
if (i*prij>n)break;
notprime[i*prij]=1;
if (i%prij==0)break;
}
}
}
}
namespace m{
}
signed main(){
return 0;
}
写的比较屎,勿喷qwq
回复
共 23 条回复,欢迎继续交流。
正在加载回复...