关于scanf与cin哪个快的问题,scanf与cin

 

一开始入c++的时候成天跑cin,cout

直到有一天用cin,cout超时

才知道scanf比cin快的多

但是后来又听说加了ios::sync_with_stdio(false);的cin跟飞一样

那么到底哪个快呢?

咱们来做个小测试

 

题目选择:

     树状数组模板2(因为这题数据比较大)

 

首先是龟速的cin与cout

图片 1

成功的T掉三个点

=.=

 

那么scanf呢??

图片 2

 

完美的完成任务!!

 

 

身负众望的ios::sync_with_stdio(false);呢??

 

 

 

见证奇迹的时刻。。。

 

 

 

图片 3

速度虽然不及scanf

但是也是可以AC的

 

另外不得不提一下超神的读入优化

图片 4

快于scanf

 

 

综上所述:

如果实在懒得敲读入优化

还是乖乖的用scanf吧。。

 

 

附代码:

图片 5 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 using namespace std; 5 const int MAXN=500001;
6 int n,m; 7 int a[MAXN]; 8 int tree[MAXN]; 9 int lowbit(int p) 10
{return p&(-p);} 11 12 void interval_increase(int x,int v) 13 { 14
for(int i=x;i>0;i=i-lowbit(i)) 15 { 16 tree[i]+=v; 17 } 18 } 19 20
int point_ask(int p) 21 { 22 int ans=a[p]; 23 for(int
i=p;i<=n;i=i+lowbit(i)) 24 { 25 ans=ans+tree[i]; 26 } 27 return
ans; 28 } 29 int main() 30 { 31 //ios::sync_with_stdio(false); 32
cin>>n>>m; 33 for(int i=1;i<=n;i++) 34 cin>>a[i];
35 for(int i=1;i<=m;i++) 36 { 37 int how; 38 cin>>how; 39
if(how==1)// 增加 40 { 41 int x,y,v; 42 cin>>x>>y>>v;
43 interval_increase(y,v); 44 interval_increase(x-1,-v); 45 } 46 else
47 { 48 int p; 49 cin>>p; 50
cout<<point_ask(p)<<endl; 51 } 52 } 53 return 0; 54 } 龟速的cin
图片 6 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 using namespace std; 5 const int MAXN=500001;
6 int n,m,p; 7 int tree[MAXN];// 8 int lowbit(int p) 9 { 10 return
p&(-p); 11 } 12 void point_increase(int w,int v) 13 { 14 for(int
i=w;i<=n;i=i+lowbit(i)) 15 tree[i]=tree[i]+v; 16 return ; 17 } 18
int interval_ask(int x) 19 { 20 int ans=0; 21 for(int
i=x;i!=0;i=i-lowbit(i)) 22 { 23 ans=ans+tree[i]; 24 } 25 return ans;
26 } 27 int main() 28 { 29 scanf(“%d%d”,&n,&m); 30 for(int
i=1;i<=n;i++) 31 { 32 scanf(“%d”,&p); 33 point_increase(i,p); 34 }
35 for(int i=1;i<=m;i++) 36 { 37 scanf(“%d”,&p); 38 if(p==1)// 加 39
{ 40 int x,y; 41 scanf(“%d%d”,&x,&y); 42 point_increase(x,y); 43 } 44
else// 求和 45 { 46 int x,y; 47 scanf(“%d%d”,&x,&y); 48
printf(“%dn”,interval_ask(y)-interval_ask(x-1)); 49 } 50 } 51 return
0; 52 } nice的scanf
图片 7 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 using namespace std; 5 const int MAXN=500001;
6 int n,m; 7 int a[MAXN]; 8 int tree[MAXN]; 9 int lowbit(int p) 10
{return p&(-p);} 11 12 void interval_increase(int x,int v) 13 { 14
for(int i=x;i>0;i=i-lowbit(i)) 15 { 16 tree[i]+=v; 17 } 18 } 19 20
int point_ask(int p) 21 { 22 int ans=a[p]; 23 for(int
i=p;i<=n;i=i+lowbit(i)) 24 { 25 ans=ans+tree[i]; 26 } 27 return
ans; 28 } 29 int main() 30 { 31 ios::sync_with_stdio(false); 32
cin>>n>>m; 33 for(int i=1;i<=n;i++) 34 cin>>a[i];
35 for(int i=1;i<=m;i++) 36 { 37 int how; 38 cin>>how; 39
if(how==1)// 增加 40 { 41 int x,y,v; 42 cin>>x>>y>>v;
43 interval_increase(y,v); 44 interval_increase(x-1,-v); 45 } 46 else
47 { 48 int p; 49 cin>>p; 50
cout<<point_ask(p)<<endl; 51 } 52 } 53 return 0; 54 } 还不错的cin优化
图片 8 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 using namespace std; 5 const int MAXN=500001;
6 int n,m; 7 int a[MAXN]; 8 int tree[MAXN]; 9 int lowbit(int p) 10
{return p&(-p);} 11 12 int read(int &n) 13 { 14 char ch=’ ‘;int q=0,w=1;
15 for(;(ch!=’-‘)&&((ch<‘0′)||(ch>’9′));ch=getchar()); 16
if(ch==’-‘)w=-1,ch=getchar(); 17 for(;ch>=’0′ &&
ch<=’9’;ch=getchar())q=q*10+ch-48; 18 n=q*w; return n; 19 } 20 21
void interval_increase(int x,int v) 22 { 23 for(int
i=x;i>0;i=i-lowbit(i)) 24 { 25 tree[i]+=v; 26 } 27 } 28 29 int
point_ask(int p) 30 { 31 int ans=a[p]; 32 for(int
i=p;i<=n;i=i+lowbit(i)) 33 { 34 ans=ans+tree[i]; 35 } 36 return
ans; 37 } 38 int main() 39 { 40 ios::sync_with_stdio(false); 41
read(n); 42 read(m); 43 for(int i=1;i<=n;i++) 44 read(a[i]); 45
for(int i=1;i<=m;i++) 46 { 47 int how; 48 read(how); 49 if(how==1)//
增加 50 { 51 int x,y,v; 52 read(x); 53 read(y); 54 read(v); 55
interval_increase(y,v); 56 interval_increase(x-1,-v); 57 } 58 else 59
{ 60 int p; 61 read(p); 62 printf(“%d”,point_ask(p)); 63
putchar(‘n’); 64 } 65 } 66 return 0; 67 } 飞速的读入优化

 

一开始入c++的时候成天跑cin,cout 直到有一天用cin,cout超时
才知道scanf比cin快的多 但是后来又听说加…

 

P2023 [AHOI2009]维护序列,p2023ahoi2009

老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。
有长为N的数列,不妨设为a1,a2,…,aN 。有如下三种操作形式:
(1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值;
(3)询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模P的值。

树状数组

(pos^(pos-1))&pos==pos&(-pos)两种写法都行

单点添加,区间查询

#include<cstdio>

#include<iostream>

#define M 500010

using namespace std;

int a[M],tarr[M],n,m;

int Qry_tarr(int pos)

{

    int sum=0;

    while(pos)

    {

        sum+=tarr[pos];

        pos-=(pos^(pos-1))&pos;

    }

    return sum;

}

void Add_tarr(int pos,int delta)

{

    while(pos<=n)

    {

        tarr[pos]+=delta;

        pos+=(pos^(pos-1))&pos;

    }

}

int main()

{

    scanf(“%d%d”,&n,&m);

    for(int i=1;i<=n;i++)

      scanf(“%d”,&a[i]);

    for(int i=1;i<=n;i++)

      Add_tarr(i,a[i]);

    int flag,x,y;

    for(int i=1;i<=m;i++)

    {

        scanf(“%d%d%d”,&flag,&x,&y);

        if(flag==1)Add_tarr(x,y);

        else printf(“%dn”,Qry_tarr(y)-Qry_tarr(x-1));

    }

    return 0;

}

区间修改,单点查询(差分)

#include<iostream>//区间修改,单点查询

using namespace std;

#define M 500010

int tr[M],b[M],n;

int search(int pos)

{

    int sum=0;

    while(pos)

    {

        sum+=tr[pos];

        pos-=(pos^(pos-1))&pos;

    }

    return sum;

}

void add(int pos,int v)

{

    while(pos<=n)

    {

        tr[pos]+=v;

        pos+=(pos^(pos-1))&pos;

    }

}

int main()

{

    cin>>n;

    int a=0,c=0;

    for(int i=1;i<=n;i++)

    {

        cin>>a;

        b[i]=a-c;

        c=a;

    }

    for(int i=1;i<=n;i++)

        add(i,b[i]);

    cin>>a;

    cout<<search(a);

}

输入输出格式

输入格式:

 

第一行两个整数N和P(1≤P≤1000000000)。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN,
(0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M,表示操作总数。从第四行开始每行描述一个操作,输入的操作有以下三种形式:
操作1:“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c
(1≤t≤g≤N,0≤c≤1000000000)。 操作2:“2 t g
c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c
(1≤t≤g≤N,0≤c≤1000000000)。 操作3:“3 t
g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。
同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。

 

输出格式:

 

对每个操作3,按照它在输入中出现的顺序,依次输出一行一个整数表示询问结果。

 

线段树

线段树5种基本操作代码:

#include<cstdio>

using namespace std;

int n,p,a,b,m,x,y,ans;

struct node

{

    int l,r,w,f;

}tree[400001];

inline void build(int k,int ll,int rr)//建树

{

    tree[k].l=ll,tree[k].r=rr;

    if(tree[k].l==tree[k].r)

    {

        scanf(“%d”,&tree[k].w);

        return;

    }

    int m=(ll+rr)/2;

    build(k*2,ll,m);

    build(k*2+1,m+1,rr);

    tree[k].w=tree[k*2].w+tree[k*2+1].w;

}

inline void down(int k)//标记下传

{

    tree[k*2].f+=tree[k].f;

    tree[k*2+1].f+=tree[k].f;

    tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);

   
tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);

    tree[k].f=0;

}

inline void ask_point(int k)//单点查询

{

    if(tree[k].l==tree[k].r)

    {

        ans=tree[k].w;

        return ;

    }

    if(tree[k].f) down(k);

    int m=(tree[k].l+tree[k].r)/2;

    if(x<=m) ask_point(k*2);

    else ask_point(k*2+1);

}

inline void change_point(int k)//单点修改

{

    if(tree[k].l==tree[k].r)

    {

        tree[k].w+=y;

        return;

    }

    if(tree[k].f) down(k);

    int m=(tree[k].l+tree[k].r)/2;

    if(x<=m) change_point(k*2);

    else change_point(k*2+1);

    tree[k].w=tree[k*2].w+tree[k*2+1].w;

}

inline void ask_interval(int k)//区间查询

{

    if(tree[k].l>=a&&tree[k].r<=b)

    {

        ans+=tree[k].w;

        return;

    }

    if(tree[k].f) down(k);

    int m=(tree[k].l+tree[k].r)/2;

    if(a<=m) ask_interval(k*2);

    if(b>m) ask_interval(k*2+1);

}

inline void change_interval(int k)//区间修改

{

    if(tree[k].l>=a&&tree[k].r<=b)

    {

        tree[k].w+=(tree[k].r-tree[k].l+1)*y;

        tree[k].f+=y;

        return;

    }

    if(tree[k].f) down(k);

    int m=(tree[k].l+tree[k].r)/2;

    if(a<=m) change_interval(k*2);

    if(b>m) change_interval(k*2+1);

    tree[k].w=tree[k*2].w+tree[k*2+1].w;

}

int main()

{

    scanf(“%d”,&n);//n个节点

    build(1,1,n);//建树

    scanf(“%d”,&m);//m种操作

    for(int i=1;i<=m;i++)

    {

        scanf(“%d”,&p);

        ans=0;

        if(p==1)

        {

            scanf(“%d”,&x);

            ask_point(x);//单点查询,输出第x个数

            printf(“%d”,ans);

        }

        else if(p==2)

        {

            scanf(“%d%d”,&x,&y);

            change_point(1);//单点修改

        }

        else if(p==3)

        {

            scanf(“%d%d”,&a,&b);//区间查询

            ask_interval(1);

            printf(“%dn”,ans);

        }

        else

        {

             scanf(“%d%d%d”,&a,&b,&y);//区间修改

             change_interval(1);

        }

    }

}

输入输出样例

输入样例#1:

7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7

输出样例#1:

2
35
8

树链剖分

【题目描述】

给你由N个结点组成的树。树的节点被编号为1到N,边被编号为1到N-1。每一条边有一个权值。然后你要在树上执行一系列指令。指令可以是如下三种之一:

CHANGE i v:将第i条边的权值改成v。

NEGATE a b:将点a到点b路径上所有边的权值变成其相反数。

QUERY a b:找出点a到点b路径上各边的最大权值。

【输入格式】

输入文件的第一行有一个整数N(N<=10000)。

接下来N-1行每行有三个整数a,b,c,代表点a和点b之间有一条权值为c的边。这些边按照其编号从小到大给出。

接下来是若干条指令(不超过10^5条),都按照上面所说的格式。

输入文件的最后一行是”DONE”.

【输出格式】

对每个“QUERY”指令,输出一行,即路径上各边的最大权值。

【样例输入】

3

1 2 1

2 3 2

QUERY 1 2

CHANGE 1 3

QUERY 1 2

DONE

【样例输出】

1

3

【来源】

POJ 3237 Tree

难点在于取相反数操作

记录下最大值和最小值,有取相反数操作时,就把两个值变成相反数,再交换两数的值就ok,然后给这个区间打上标记(线段树的lazy标记),以后访问或更改值时记得下传标记就好。

 

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAXN = 100010;

struct Edge{

    int to,next;

}edge[MAXN*2];

int head[MAXN],tot;

int top[MAXN];//top[v]表示v所在的重链的顶端节点

int fa[MAXN]; //父亲节点

int deep[MAXN];//深度

int num[MAXN];//num[v]表示以v为根的子树的节点数

int p[MAXN];//p[v]表示v与其父亲节点的连边在线段树中的位置

int fp[MAXN];//和p数组相反

int son[MAXN];//重儿子

int pos;

void init(){

    tot = 0;

    memset(head,-1,sizeof(head));

    pos = 0;

    memset(son,-1,sizeof(son));

}

void addedge(int u,int v){

    edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;

}

void dfs1(int u,int v,int d){

    deep[v]=d;

    fa[v]=u;

    num[v]=1;

    for(int i=head[v];i!=-1;i=edge[i].next){

        int to=edge[i].to;

        if(to==u)continue;

        dfs1(v,to,d+1);

        num[v]+=num[to];

        if(son[v]==-1||num[son[v]]<num[to])son[v]=to;

    }

}

void dfs2(int u,int v){

    top[u]=v;

    p[u]=pos++;

    if(son[u]==-1)return;

    dfs2(son[u],v);

    for(int i=head[u];i!=-1;i=edge[i].next){

        int to=edge[i].to;

        if(to==fa[u]||to==son[u])continue;

        dfs2(to,to);

    }

}

 

//线段树

struct Node{

    int l,r;

    int Max;

    int Min;

    int ne;

}tr[MAXN*3];

void build(int i,int l,int r){

    tr[i].l = l;

    tr[i].r = r;

    tr[i].Max = 0;

    tr[i].Min = 0;

    tr[i].ne = 0;

    if(l == r)return;

    int mid = (l+r)/2;

    build(i<<1,l,mid);

    build((i<<1)|1,mid+1,r);

}

void push_up(int i)

{

    tr[i].Max = max(tr[i<<1].Max,tr[(i<<1)|1].Max);

    tr[i].Min = min(tr[i<<1].Min,tr[(i<<1)|1].Min);

}

void push_down(int i){

 

    if(tr[i].l == tr[i].r)return;

    if(tr[i].ne)

    {

        tr[i<<1].Max = -tr[i<<1].Max;

        tr[i<<1].Min = -tr[i<<1].Min;

        swap(tr[i<<1].Min,tr[i<<1].Max);

        tr[(i<<1)|1].Max = -tr[(i<<1)|1].Max;

        tr[(i<<1)|1].Min = -tr[(i<<1)|1].Min;

        swap(tr[(i<<1)|1].Max,tr[(i<<1)|1].Min);

        tr[i<<1].ne ^= 1;

        tr[(i<<1)|1].ne ^= 1;

        tr[i].ne = 0;

    }

}

void update(int i,int k,int val){ // 更新线段树的第k个值为val

 

    if(tr[i].l == k && tr[i].r == k)

    {

        tr[i].Max = val;

        tr[i].Min = val;

        tr[i].ne = 0;

        return;

    }

    push_down(i);

    int mid = (tr[i].l + tr[i].r)/2;

    if(k <= mid)update(i<<1,k,val);

    else update((i<<1)|1,k,val);

    push_up(i);

}

 

void ne_update(int i,int l,int r){

    if(tr[i].l==l&&tr[i].r==r){

        tr[i].Max=-tr[i].Max;tr[i].Min=-tr[i].Min;

        swap(tr[i].Max,tr[i].Min);

        tr[i].ne^=1;return;

    }

    push_down(i);

    int mid=(tr[i].l+tr[i].r)>>1;

    if(r<=mid)ne_update(i<<1,l,r);

    else if(l>mid)ne_update((i<<1)|1,l,r);

    else
ne_update(i<<1,l,mid),ne_update((i<<1)|1,mid+1,r);

    tr[i].Min=min(tr[i<<1].Min,tr[(i<<1)|1].Min);

    tr[i].Max=max(tr[i<<1].Max,tr[(i<<1)|1].Max);

}

int query(int i,int l,int r){  //查询线段树中[l,r] 的最大值

 

    if(tr[i].l == l && tr[i].r == r)

        return tr[i].Max;

    push_down(i);

    int mid = (tr[i].l + tr[i].r)/2;

    if(r <= mid)return query(i<<1,l,r);

    else if(l > mid)return query((i<<1)|1,l,r);

    else return
max(query(i<<1,l,mid),query((i<<1)|1,mid+1,r));

    push_up(i);

}

int findmax(int u,int v){//查询u->v边的最大值

 

    int f1 = top[u], f2 = top[v];

    int tmp = -100000000;

    while(f1 != f2)

    {

        if(deep[f1] < deep[f2])

        {

            swap(f1,f2);

            swap(u,v);

        }

        tmp = max(tmp,query(1,p[f1],p[u]));

        u = fa[f1]; f1 = top[u];

    }

    if(u == v)return tmp;

    if(deep[u] > deep[v]) swap(u,v);

    return max(tmp,query(1,p[son[u]],p[v]));

}

void Negate(int u,int v){

    int f1=top[u],f2=top[v];

    while(f1!=f2){

        if(deep[f1]<deep[f2])swap(f1,f2),swap(u,v);

        ne_update(1,p[f1],p[u]);

        u=fa[f1];f1=top[u];

    }

    if(u==v)return;

    if(deep[u]>deep[v])swap(u,v);

    ne_update(1,p[son[u]],p[v]);

    return;

}

int E[MAXN][3];

int main()

{

    //freopen(“Cola.txt”,”r”,stdin);

    freopen(“maintaintree.in”,”r”,stdin);

    freopen(“maintaintree.out”,”w”,stdout);

    int T,n;

    T=1;

    while(T–){

        init();

        scanf(“%d”,&n);

        for(int i=0;i<n-1;i++){

            scanf(“%d%d%d”,&E[i][0],&E[i][1],&E[i][2]);

            addedge(E[i][0],E[i][1]);

            addedge(E[i][1],E[i][0]);

        }

        dfs1(0,1,0);

        dfs2(1,1);

        build(1,0,pos-1);

        for(int i=0;i<n-1;i++){

           
if(deep[E[i][0]]>deep[E[i][1]])swap(E[i][0],E[i][1]);

            update(1,p[E[i][1]],E[i][2]);

        }

        char ch[10];

        int u,v;

        while(1){

            scanf(“%s”,ch);

            if(ch[0]==’D’)break;

            scanf(“%d%d”,&u,&v);

            if(ch[0]==’Q’)printf(“%dn”,findmax(u,v));

            else if(ch[0]==’C’)update(1,p[E[u-1][1]],v);

            else Negate(u,v);

        }

    }

    return 0;

}

说明

【样例说明】

初始时数列为(1,2,3,4,5,6,7)。

经过第1次操作后,数列为(1,10,15,20,25,6,7)。

对第2次操作,和为10+15+20=45,模43的结果是2。

经过第3次操作后,数列为(1,10,24,29,34,15,16}

对第4次操作,和为1+10+24=35,模43的结果是35。

对第5次操作,和为29+34+15+16=94,模43的结果是8。

测试数据规模如下表所示

数据编号 1 2 3 4 5 6 7 8 9 10

N= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000

M= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000

Source: Ahoi 2009

调了一个半小时,调不出来

不调了、、

图片 9 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 #include<cmath> 5
#include<algorithm> 6 #define lli long long 7 using namespace
std; 8 const int MAXN=500001; 9 lli n,m,mod,ans; 10 void read(lli & n)
11 { 12 char c=’+’;lli x=0;bool flag=0; 13 while(c<‘0’||c>’9′) 14
{c=getchar();if(c==’-‘)flag=1;} 15 while(c>=’0’&&c<=’9’) 16
{x=x*10+(c-48),c=getchar();} 17 flag==1?n=-x:n=x; 18 } 19 struct node
20 { 21 lli l,r,w,k,fc,fj; 22 }tree[MAXN*4]; 23 void pushdown(lli
k,lli ll,lli rr,lli mid) 24 { 25
tree[k<<1].w*=tree[k].fc%mod; 26
tree[k<<1|1].w*=tree[k].fc%mod; 27
tree[k<<1].w=(tree[k<<1].w+tree[k].fj*(mid-ll+1))%mod;
28
tree[k<<1|1].w=(tree[k<<1|1].w+tree[k].fj*(rr-mid))%mod;
29 30 tree[k<<1].fc%=mod;tree[k<<1|1].fc%=mod; 31
tree[k<<1].fj%=mod;tree[k<<1|1].fj%=mod; 32
tree[k<<1].w%=mod;tree[k<<1|1].w%=mod; 33 34
tree[k<<1].fc*=tree[k].fc%mod;tree[k<<1|1].fc*=tree[k].fc%mod;
35
tree[k<<1].fj*=tree[k].fc%mod;tree[k<<1|1].fj*=tree[k].fc%mod;
36 tree[k<<1].fj=(tree[k<<1].fj+tree[k].fj)%mod; 37
tree[k<<1|1].fj=(tree[k<<1|1].fj+tree[k].fj)%mod; 38
39 40 tree[k].fc=1; 41 tree[k].fj=0; 42 43 44
tree[k<<1].fc%=mod;tree[k<<1|1].fc%=mod; 45
tree[k<<1].fj%=mod;tree[k<<1|1].fj%=mod; 46
tree[k<<1].w%=mod;tree[k<<1|1].w%=mod; 47 } 48 void
update(lli k) 49 { 50
tree[k].w=(tree[k<<1].w+tree[k<<1|1].w)%mod; 51 } 52
void build_tree(lli ll,lli rr,lli k) 53 { 54
tree[k].l=ll;tree[k].r=rr;tree[k].k=k; 55
tree[k].fc=1;tree[k].fj=0; 56 if(tree[k].l==tree[k].r) 57 { 58
read(tree[k].w); 59 tree[k].w%=mod; 60 return ; 61 } 62 lli
mid=(ll+rr)>>1; 63 build_tree(ll,mid,k<<1); 64
build_tree(mid+1,rr,k<<1|1); 65 update(k); 66 } 67 void
interval_mul(lli k,lli ll,lli rr,lli v) 68 { 69
if(ll>tree[k].r||rr<tree[k].l) 70 return ; 71
if(tree[k].l>=ll&&tree[k].r<=rr) 72 { 73 tree[k].w*=v%mod;
74 tree[k].fc*=v%mod; 75 tree[k].fj*=v%mod; 76 return ; 77 } 78
lli mid=(tree[k].l+tree[k].r)>>1; 79
pushdown(k,tree[k].l,tree[k].r,mid); 80 if(ll<=mid) 81
interval_mul(k<<1,ll,rr,v); 82 if(rr>mid) 83
interval_mul(k<<1|1,ll,rr,v); 84 update(k); 85 } 86 void
interval_add(lli k,lli ll,lli rr,lli v) 87 { 88
if(ll>tree[k].r||rr<tree[k].l) 89 return ; 90
if(tree[k].l>=ll&&tree[k].r<=rr) 91 { 92
tree[k].w=(tree[k].w+v*(tree[k].r-tree[k].l+1))%mod; 93
//tree[k].fc*=v%mod; 94 tree[k].fj=(tree[k].fj+v)%mod; 95 return
; 96 } 97 lli mid=(tree[k].l+tree[k].r)>>1; 98
pushdown(k,tree[k].l,tree[k].r,mid); 99 if(ll<=mid) 100
interval_add(k<<1,ll,rr,v); 101 if(rr>mid) 102
interval_add(k<<1|1,ll,rr,v); 103 update(k); 104 105 } 106 void
interval_ask(lli k,lli ll,lli rr) 107 { 108
if(ll>tree[k].r||rr<tree[k].l) 109 return ; 110
if(tree[k].l>=ll&&tree[k].r<=rr) 111 { 112
ans=(ans+tree[k].w)%mod; 113 return ; 114 } 115 lli
mid=(tree[k].l+tree[k].r)>>1; 116
pushdown(k,tree[k].l,tree[k].r,mid); 117 if(ll<=mid) 118
interval_ask(k<<1,ll,rr); 119 if(rr>mid) 120
interval_ask(k<<1|1,ll,rr); 121 update(k); 122 } 123 int main()
124 { 125 read(n);read(mod); 126 build_tree(1,n,1); 127 read(m); 128
for(lli i=1;i<=m;i++) 129 { 130 lli how,x,y,c; 131 read(how); 132
if(how==1) 133 { 134 read(x);read(y);read(c); 135
interval_mul(1,x,y,c%mod);//乘 136 } 137 else if(how==2) 138 { 139
read(x);read(y);read(c); 140 interval_add(1,x,y,c%mod);// 加 141 } 142
else if(how==3) 143 { 144 ans=0; 145 read(x);read(y); 146
interval_ask(1,x,y); 147 printf(“%lldn”,ans); 148 } 149 } 150 return
0; 151 } 60分
图片 10 1
#include<iostream> 2 #include<cstdio> 3 #define lli long
long int 4 #define re register 5 #define LL long long 6 #define M
500000 7 using namespace std; 8 void read(lli & n) 9 { 10 char c=’+’;lli
x=0;bool flag=0; 11 while(c<‘0’||c>’9′) 12
{c=getchar();if(c==’-‘)flag=1;} 13 while(c>=’0’&&c<=’9’) 14
{x=x*10+(c-48),c=getchar();} 15 flag==1?n=-x:n=x; 16 } 17 LL
mogician,a[M/2+1]; 18 int n; 19 struct Tree{ 20 LL sum,add,mult; 21
}tr[M+1]; 22 inline void build(int k,int l,int r){ 23 tr[k].mult=1;
24 if(l==r){ 25 tr[k].sum=a[l]; 26 return ; 27 } 28 int
mid=(l+r)>>1; 29 build(k<<1,l,mid); 30
build(k<<1|1,mid+1,r); 31
tr[k].sum=(tr[k<<1].sum+tr[k<<1|1].sum)%mogician; 32 }
33 inline void Work_Out(int k,int l,int r,LL mu,LL ad){ 34
tr[k].add=(tr[k].add*mu+ad)%mogician; 35
tr[k].mult=(tr[k].mult*mu)%mogician; 36
tr[k].sum=(tr[k].sum*mu+(r-l+1)*ad)%mogician; 37 } 38 inline void
Push_Down(int k,int l,int r){ 39 if(tr[k].add==0&&tr[k].mult==1) 40
return ; 41 int mid=(l+r)>>1; 42
Work_Out(k<<1,l,mid,tr[k].mult,tr[k].add); 43
Work_Out(k<<1|1,mid+1,r,tr[k].mult,tr[k].add); 44
tr[k].add=0; 45 tr[k].mult=1; 46 } 47 inline void Lazy_Tag(int
k,int l,int r,int x,int y,LL mu,LL ad){ 48 if(x<=l&&r<=y){ 49
Work_Out(k,l,r,mu,ad); 50 return ; 51 } 52 Push_Down(k,l,r); 53 int
mid=(l+r)>>1; 54 if(x<=mid) 55
Lazy_Tag(k<<1,l,mid,x,y,mu,ad); 56 if(mid<y) 57
Lazy_Tag(k<<1|1,mid+1,r,x,y,mu,ad); 58
tr[k].sum=(tr[k<<1].sum+tr[k<<1|1].sum)%mogician; 59 }
60 inline LL Q(int k,int l,int r,int x,int y){ 61 if(x<=l&&r<=y)
62 return tr[k].sum%mogician; 63 Push_Down(k,l,r); 64 int
mid=(l+r)>>1; 65 return
((x<=mid?Q(k<<1,l,mid,x,y)%mogician:0)+(mid<y?Q(k<<1|1,mid+1,r,x,y)%mogician:0))%mogician;
66 } 67 int m,d,x,y; 68 LL k; 69 int main(){ 70 71
scanf(“%lld%lld”,&n,&mogician); 72 for(re int i=1;i<=n;i++){ 73
scanf(“%lld”,&a[i]); 74 a[i]%=mogician; 75 } 76 build(1,1,n); 77
scanf(“%d”,&m); 78 for(re int i=1;i<=m;i++){ 79
scanf(“%d%d%d”,&d,&x,&y); 80 if(d==3) 81 printf(“%lldn”,Q(1,1,n,x,y));
82 else{ 83 scanf(“%lld”,&k); 84 k%=mogician; 85
d==1?Lazy_Tag(1,1,n,x,y,k,0):Lazy_Tag(1,1,n,x,y,1,k); 86 } 87 } 88
return 0; 89 } AC

 

[AHOI2009]维护序列,p2023ahoi2009
老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。
有长为N的数列,不妨设为a1,a2,,…

主席树

查询区间第k小

Sample Input

7 3

1 5 2 6 3 7 4

2 5 3

4 4 1

1 7 3

Sample Output

5

6

3

 

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

 

using namespace std;

const int maxn=100005;

const int maxnn=10000000;

int root[maxn],ls[maxnn],rs[maxnn],cnt[maxnn],tot;

int sz[maxn],hash[maxn];

void build(int cur,int l,int r)

{

    cur=tot++;

    cnt[cur]=0;

    if(l!=r)

    {

        int mid=(l+r)/2;

        build(ls[cur],l,mid);

        build(rs[cur],mid+1,r);

    }

}

void update(int pre,int ps,int &cur,int l,int r)

{

    cur=tot++;

    cnt[cur]=cnt[pre]+1;

    ls[cur]=ls[pre];rs[cur]=rs[pre];

    if(l==r)return ;

    int mid=(l+r)/2;

    if(ps<=mid)update(ls[pre],ps,ls[cur],l,mid);

    else update(rs[pre],ps,rs[cur],mid+1,r);

}

int query(int lt,int rt,int l,int r,int k)

{

    if(l==r)return l;

    int mid=(l+r)/2,cha=cnt[ls[rt]]-cnt[ls[lt]];

    if(k<=cha)return query(ls[lt],ls[rt],l,mid,k);

    else return query(rs[lt],rs[rt],mid+1,r,k-cha);

}

int main()

{

    int m,n,l,r,k;

    while(scanf(“%d%d”,&n,&m)==2)

    {

        for(int i=1;i<=n;++i)

        {

            scanf(“%d”,sz+i);

            hash[i]=sz[i];

        }

        sort(hash+1,hash+n+1);

        int siz=unique(hash+1,hash+1+n)-hash-1;

        for(int i=1;i<=n;++i)

            sz[i]=lower_bound(hash+1,hash+1+siz,sz[i])-hash;

        tot=0;

        build(root[0],1,siz);

        for(int i=1;i<=n;++i)

            update(root[i-1],sz[i],root[i],1,siz);

        while(m–)

        {

            scanf(“%d%d%d”,&l,&r,&k);

           
printf(“%dn”,hash[query(root[l-1],root[r],1,siz,k)]);

        }

    }

    return 0;

}

字典树Trie树

1、查询是否出现

/*

  trie tree的储存方式:将字母储存在边上,边的节点连接与它相连的字母

  trie[rt][x]=tot:rt是上个节点编号,x是字母,tot是下个节点编号

*/

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define maxn 2000010

using namespace std;

int tot=1,n;

int trie[maxn][26];

//bool isw[maxn];查询整个单词用

void insert(char *s,int rt)

{

    for(int i=0;s[i];i++)

    {

        int x=s[i]-‘a’;

        if(trie[rt][x]==0)//现在插入的字母在之前同一节点处未出现过

        {

            trie[rt][x]=++tot;//字母插入一个新的位置,否则不做处理

        }

        rt=trie[rt][x];//为下个字母的插入做准备 

    }

   
/*isw[rt]=true;标志该单词末位字母的尾结点,在查询整个单词时用到*/

}

bool find(char *s,int rt)

{

    for(int i=0;s[i];i++)

    {

        int x=s[i]-‘a’;

        if(trie[rt][x]==0)return
false;//以rt为头结点的x字母不存在,返回0

        rt=trie[rt][x];//为查询下个字母做准备

    }

    return true;

    //查询整个单词时,应该return isw[rt]

}

char s[22];

int main()

{

    tot=0;

    int rt=1;

    scanf(“%d”,&n);

    for(int i=1;i<=n;i++)

    {

        cin>>s;

        insert(s,rt);

    }

    scanf(“%d”,&n);

    for(int i=1;i<=n;i++)

    {

        cin>>s;

        if(find(s,rt))printf(“YESn”);

        else printf(“NOn”);

    }

    return 0;

}

2、查询前缀出现次数

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

int trie[400001][26],len,root,tot,sum[400001];

bool p;

int n,m;

char s[11];

void insert()

{

    len=strlen(s);

    root=0;

    for(int i=0;i<len;i++)

    {

        int id=s[i]-‘a’;

        if(!trie[root][id]) trie[root][id]=++tot;

        sum[trie[root][id]]++;//前缀后移一个位置保存

        root=trie[root][id];

    }

}

int search()

{

    root=0;

    len=strlen(s);

    for(int i=0;i<len;i++)

    {

        int id=s[i]-‘a’;

        if(!trie[root][id]) return 0;

        root=trie[root][id];

    }//root经过此循环后变成前缀最后一个字母所在位置的后一个位置

    return
sum[root];//因为前缀后移了一个保存,所以此时的sum[root]就是要求的前缀出现的次数

}

int main()

{

    scanf(“%d”,&n);

    for(int i=1;i<=n;i++)

    {

        cin>>s;

        insert();

    }

    scanf(“%d”,&m);

    for(int i=1;i<=m;i++)

    {

        cin>s;

        printf(“%dn”,search());

    }

}

加权并查集

题目大意:
有块积木,开始时它们都属于不同的集合。
然后输入p,表示有p个操作。每个操作都有一个t,如果t==M,那么输入x,y,把x所在集合的所有积木,都堆到y所在集合的上面;如果t==C,那么输入x,查询并输出x下面有多少个积木(不包括x本身)。
解题思路:加权并查集
先设2个数组,under[i]=j表示在积木i下面有j个积木;tot[i]=j表示i所在集合一共有j个积木。

 

由此可以看出,如果我们要把x摞到y的上面,

在合并操作时,x的下面多了y所在集合的全体,所以under[x]=under[x]+tot[y];x的father指向y,y所代表的集合总数多了x所在集合的全体,所以tot[y]=tot[x]+tot[y]

上面还更新了tot[x]=0,这个在代码中更不更新无所谓,并查集合并操作合并祖先节点,x的father指向了y,x不会再作为祖先节点出现

在查询祖先节点时,我们需要维护under[]

 

 

在路径压缩中更新under时,要先记录下i的祖先节点,在递归回溯时先加上i原父节点的under,再把i的父节点更新为祖先节点。

#include<cstdio>

#include<iostream>

using namespace std;

int p,father_x,father_y;

char c;

int x,y,un;

int under[30001],tot[30001],fa[30001];//under:下面有几个积木 
tot:集合一共有几个积木

int find(int i)

{

    //先更新under再路径压缩

    if(fa[i]!=i)

    {

        int tmp=find(fa[i]);

        under[i]+=under[fa[i]];

        fa[i]=tmp;

    }

    return fa[i];

}

void unionn()//x摞到y的上面

{

    under[father_x]+=tot[father_y];

    tot[father_y]+=tot[father_x];

    fa[father_x]=father_y;

}

int main()

{

    scanf(“%d”,&p);

    for(int i=0;i<=30000;i++) tot[i]=1,fa[i]=i;

    while(p–)

    {

        cin>>c;

        if(c==’M’)

        {

            scanf(“%d%d”,&x,&y);

            father_y=find(y);

            father_x=find(x);

            if(father_x!=father_y)

            unionn();

        }

        else

        {

            scanf(“%d”,&x);

            find(x);

            printf(“%dn”,under[x]);

        }

    }

}

二分图

二分图匹配可以分4种类型

最大匹配数:最大匹配的匹配边的数目

最小点覆盖数:选取最少的点,使任意一条边至少有一个端点被选择

最大独立数:选取最多的点,使任意所选两点均不相连

最小路径覆盖数:对于一个
DAG(有向无环图),选取最少条路径,使得每个顶点属于且仅属于一条路径。路径长可以为
0(即单个点)。

定理1:最大匹配数 = 最小点覆盖数(这是 Konig
定理)

定理2:最大匹配数 = 最大独立数

定理3:最小路径覆盖数 = 顶点数 – 最大匹配数

1.最大匹配数

最大匹配的匹配边的数目

洛谷P3386
【模板】二分图匹配

P3386 【模板】二分图匹配

题目背景

二分图

题目描述

给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数

输入输出格式

输入格式:

第一行,n,m,e

第二至e+1行,每行两个正整数u,v,表示u,v有一条连边

输出格式:

共一行,二分图最大匹配

输入输出样例

输入样例#1:

1 1 1

1 1

输出样例#1:

1

说明

n,m<=1000,1<=u<=n,1<=v<=m

因为数据有坑,可能会遇到v>m的情况。请把v>m的数据自觉过滤掉。

算法:二分图匹配

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 1010

using namespace std;

int n,m,e,link[maxn],re[maxn][maxn],vis[maxn],ans;

int dfs(int x){

    for(int i=1;i<=m;i++)

        if(vis[i]==0&&re[x][i]){

            vis[i]=1;

            if(link[i]==0||dfs(link[i])){

                link[i]=x;return 1;

            }

        }

    return 0;

}

int main(){

    scanf(“%d%d%d”,&n,&m,&e);

    int x,y;

    for(int i=1;i<=e;i++){

        scanf(“%d%d”,&x,&y);

        re[x][y]=1;

    }

    for(int i=1;i<=n;i++){

        memset(vis,0,sizeof(vis));

        if(dfs(i))ans++;

    }

    printf(“%d”,ans);

}

2.最小点覆盖数

选取最少的点,使任意一条边至少有一个端点被选择

有定理在,判断出一个题可以用最小点覆盖数求的时候,就直接用求最大匹配数的代码搞

poj3041Asteroids

跟上一个题按同一个套路来

题意:给出一个n*n的矩阵和矩阵上m个点,问你最少删除了多少行或列之后,点能全部消失。(联想:给出一张图上的m条边的n个相交顶点(xi,
yi),问最少用其中的几个点,就可以和所有的边相关联)

 

思路:匈牙利算法的最小覆盖问题:最小覆盖要求在一个二分图上用最少的点(x
或 y
集合的都行),让每条连接两个点集的边都至少和其中一个点关联。根据konig定理:二分图的最小顶点覆盖数等于最大匹配数。理解到这里,将(x,y)这一点,转化为x_y的一条边,把x
= a的这一边,转化为(a)这一点,剩下的就是基础的匈牙利算法实现了。

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define maxn 501

#define maxm 10010

int n,k,num,head[maxm],link[maxn],vis[maxn];

struct node{

    int to,pre;

}e[maxm];

void Insert(int from,int to){

    e[++num].to=to;

    e[num].pre=head[from];

    head[from]=num;

}

int dfs(int x){

    for(int i=head[x];i;i=e[i].pre){

        int v=e[i].to;

        if(vis[v]==0){

            vis[v]=1;

            if(link[v]==0||dfs(link[v])){

                link[v]=x;return 1;

            }

        }

    }

    return 0;

}

int main(){

    scanf(“%d%d”,&n,&k);int x,y;

    for(int i=1;i<=k;i++){

        scanf(“%d%d”,&x,&y);

        Insert(x,y);

    }

    int ans=0;

    for(int i=1;i<=n;i++){

        memset(vis,0,sizeof(vis));

        if(dfs(i))ans++;

    }

    printf(“%d”,ans);

}

3.最大独立数

选取最多的点,使任意所选两点均不相连

poj 1466 Girls and Boys

二分图的最大独立集

因为没有给出具体的男生和女生,所以可以将数据扩大一倍,即n个男生,n个女生,
根据定理,最大独立集=总数-匹配数(本题应该除以2)

给出一系列男女配对意愿信息。求一个集合中的最大人数,满足这个集合中两两的人不能配对。

Sample Input

7

0: (3) 4 5 6

1: (2) 4 6

2: (0)

3: (0)

4: (2) 0 1

5: (1) 0

6: (2) 0 1

3

0: (2) 1 2

1: (1) 0

2: (1) 0

Sample Output

5

2

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 510

using namespace std;

int link[maxn],vis[maxn],map[maxn][maxn],n;

int dfs(int x){

    for(int i=1;i<=n;i++){

        if(vis[i]==0&&map[x][i]){

            vis[i]=1;

            if(link[i]==0||dfs(link[i])){

                link[i]=x;

                return 1;

            }

        }

    }return 0;

}

int main(){

    freopen(“1.txt”,”r”,stdin);

    while(scanf(“%d”,&n)!=EOF){

        memset(map,0,sizeof(map));

        memset(link,0,sizeof(link));

        for(int i=1;i<=n;i++){

            int u,w,v;

            scanf(“%d: (%d)”,&u,&w);u++;

            for(int j=1;j<=w;j++){

                scanf(“%d”,&v);v++;

                map[u][v]=map[v][u]=1;

            }

        }

        int ans=0;

        for(int i=1;i<=n;i++){

            memset(vis,0,sizeof(vis));

            if(dfs(i))ans++;

        }

        printf(“%dn”,n-ans/2);

    }

}

4.最小路径覆盖数

对于一个
DAG(有向无环图),选取最少条路径,使得每个顶点属于且仅属于一条路径。路径长可以为
0(即单个点)。

hdu 4160 Dolls

【题意】

n个箱子

下面n行 a b c 表示箱子的长宽高

箱子可以嵌套,里面的箱子三维都要小于外面的箱子

问: 露在外头的箱子有几个

【思路】

只要成功匹配一条边,就等价于成功嵌套一个箱子,就是匹配一条边,露在外面的箱子就少一个

结果就是 n – 最大匹配数

注意一个条件: 箱子不可旋转,即 长对应长, 宽对应宽

 

然后就是一个裸的二分匹配

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define maxn 1010

#define maxm 250010

int
n,head[maxn],num,one[maxn],two[maxn],three[maxn],link[maxn];

bool vis[maxn];

struct node{

    int pre,to;

}e[maxm];

void Insert(int from,int to){

    e[++num].to=to;

    e[num].pre=head[from];

    head[from]=num;

}

int dfs(int x){

    for(int i=head[x];i;i=e[i].pre){

        int v=e[i].to;

        if(vis[v]==0){

            vis[v]=1;

            if(link[v]==0||dfs(link[v])){

                link[v]=x;return 1;

            }

        }

    }

    return 0;

}

int main(){

    while(~scanf(“%d”,&n),n){

        if(n==0)return 0;

        memset(link,0,sizeof(link));

        memset(e,0,sizeof(e));

        memset(head,0,sizeof(head));

        int sum=0;num=0;

        for(int
i=1;i<=n;i++)scanf(“%d%d%d”,&one[i],&two[i],&three[i]);

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

               
if(one[i]<one[j]&&two[i]<two[j]&&three[i]<three[j])

                    Insert(i,j+n);

        for(int i=1;i<=n;i++){

            memset(vis,0,sizeof(vis));

            if(dfs(i))sum++;

        }

        printf(“%dn”,n-sum);

    }

}

 

相关文章