板子与例题整理

1.pollared rho

例题：求区间μ+a[i]+x的积

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 #include 
  8 
  9 #include
 10 #define ll long long
 11 
 12 #define INF 0x3f3f3f3f
 13 #define maxn 10000+10
 14 #define cle(a) memset(a,0,sizeof(a))
 15 const double eps=1e-5;
 16 const int mo=998244353;
 17 using namespace std;
 18 
 19 const int S=5;//随机算法判定次数，S越大，判错概率越小
 20 //计算 (a*b)%c.   a,b都是long long的数，直接相乘可能溢出的
 21 //  a,b,c <2^63
 22 ll mult_mod(ll a,ll b,ll c)
 23 {
 24     a%=c;
 25     b%=c;
 26     ll ret=0;
 27     while(b)
 28     {
 29         if(b&1){ret+=a;ret%=c;}
 30         a<<=1;
 31         if(a>=c)a%=c;
 32         b>>=1;
 33     }
 34     return ret;
 35 }
 36 ll pow_mod(ll x,ll n,ll mod)
 37 {
 38     if(n==1)return x%mod;
 39     x%=mod;
 40     ll tmp=x;
 41     ll ret=1;
 42     while(n)
 43     {
 44         if(n&1) ret=mult_mod(ret,tmp,mod);
 45         tmp=mult_mod(tmp,tmp,mod);
 46         n>>=1;
 47     }
 48     return ret;
 49 }
 50 //以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
 51 //一定是合数返回true,不一定返回false
 52 bool check(ll a,ll n,ll x,ll t)
 53 {
 54     ll ret=pow_mod(a,x,n);
 55     ll last=ret;
 56     for(int i=1;i<=t;i++)
 57     {
 58         ret=mult_mod(ret,ret,n);
 59         if(ret==1&&last!=1&&last!=n-1) return true;//合数
 60         last=ret;
 61     }
 62     if(ret!=1) return true;
 63     return false;
 64 }
 65 // Miller_Rabin()算法素数判定
 66 //是素数返回true.(可能是伪素数，但概率极小)
 67 //合数返回false;
 68 bool Miller_Rabin(ll n)
 69 {
 70     if(n<2)return false;
 71     if(n==2)return true;
 72     if((n&1)==0) return false;//偶数
 73     ll x=n-1;
 74     ll t=0;
 75     while((x&1)==0){x>>=1;t++;}
 76     for(int i=0;i)
 77     {
 78         ll a=rand()%(n-1)+1;//rand()需要stdlib.h头文件
 79         if(check(a,n,x,t))
 80             return false;//合数
 81     }
 82     return true;
 83 }
 84 ll factor[100];//质因数分解结果（刚返回时是无序的）
 85 int tol;//质因数的个数。数组小标从0开始
 86 ll gcd(ll a,ll b)
 87 {
 88     if(a==0)return 1;//???????
 89     if(a<0) return gcd(-a,b);
 90     while(b)
 91     {
 92         ll t=a%b;
 93         a=b;
 94         b=t;
 95     }
 96     return a;
 97 }
 98 ll Pollard_rho(ll x,ll c)
 99 {
100     ll i=1,k=2;
101     ll x0=rand()%x;
102     ll y=x0;
103     while(1)
104     {
105         i++;
106         x0=(mult_mod(x0,x0,x)+c)%x;
107         ll d=gcd(y-x0,x);
108         if(d!=1&&d!=x) return d;
109         if(y==x0) return x;
110         if(i==k){y=x0;k+=k;}
111     }
112 }
113 //对n进行素因子分解
114 void findfac(ll n)
115 {
116     if(Miller_Rabin(n))//素数
117     {
118         factor[tol++]=n;
119         return;
120     }
121     ll p=n;
122     while(p>=n)p=Pollard_rho(p,rand()%(n-1)+1);
123     findfac(p);
124     findfac(n/p);
125 }
126 long long ksm(long long x,long long y)
127 {
128     long long ret=1;
129     while (y)
130     {
131         if (y&1) ret=ret*x%mo;
132         x=x*x%mo;
133         y=y>>1;
134     }
135     return ret;
136 }
137 long long a[500050],b[500050],c[500050],mu[500050],s[500050];
138 int main()
139 {
140     //freopen("test.in","r",stdin);
141     int n,m,x;
142     scanf("%d%d%d",&n,&m,&x);
143     for (int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=a[i];
144     int kk=0;
145     for (int i=1;i<=n;i++)
146     {
147         if (b[i]!=1)
148         {
149             tol=0;
150             findfac(b[i]);
151             for (int j=0;j)
152             {
153                 c[++kk]=factor[j];
154                 for (int k=1;k<=n;k++) while (b[k]%factor[j]==0) b[k]=b[k]/factor[j];
155             }
156         }
157     }
158     for (int i=1;i<=n;i++)
159     {
160         b[i]=a[i];
161         mu[i]=1;
162         for (int j=1;j<=kk;j++)
163         {
164 
165             if (b[i]%c[j]==0)
166             {
167                 int tmp=0;
168                 while (b[i]%c[j]==0)
169                 {
170                     tmp++;
171                     b[i]=b[i]/c[j];
172                 }
173                 if (tmp>=2)
174                 {
175                     mu[i]=0;
176                     break;
177                 }
178                 else mu[i]=-mu[i];
179             }
180         }
181     }
182     a[0]=1;
183     for (int i=1;i<=n;i++)
184     {
185         a[i]=(a[i]+mu[i]+x)%mo;
186         if (a[i]==0) s[i]=1,a[i]=1;
187         s[i]=s[i]+s[i-1];
188         a[i]=a[i]*a[i-1]%mo;
189     }
190     for (int i=1;i<=m;i++)
191     {
192         int l,r;
193         scanf("%d%d",&l,&r);
194         if (s[r]-s[l-1]) printf("0\n");
195         else printf("%lld\n",a[r]*ksm(a[l-1],mo-2)%mo);
196     }
197     /*ll n;
198     while(cin>>n){
199         tol=0;
200         findfac(n);
201         for(int i=0;i202         //质因子
203     }*/
204     return 0;
205 }

2.多重标记线段树

例题：区间+区间*区间赋值，求区间和，平方和，立方和

  1 #include
  2 using namespace std;
  3 const int N=1e5+10;
  4 const int mo=1e4+7;
  5 int s[4][N*4],b1[N*4],b2[N*4],b3[N*4];
  6 void build(int rt,int l,int r)
  7 {
  8     s[1][rt]=s[2][rt]=s[3][rt]=b1[rt]=b3[rt]=0;
  9     b2[rt]=1;
 10     if (l==r) return;
 11     int mid=l+r>>1;
 12     build(rt<<1,l,mid);
 13     build(rt<<1|1,mid+1,r);
 14 }
 15 void up(int rt)
 16 {
 17     s[1][rt]=(s[1][rt<<1]+s[1][rt<<1|1])%mo;
 18     s[2][rt]=(s[2][rt<<1]+s[2][rt<<1|1])%mo;
 19     s[3][rt]=(s[3][rt<<1]+s[3][rt<<1|1])%mo;
 20 }
 21 void c1(int rt,int l,int r,int c)
 22 {
 23     s[3][rt]=(s[3][rt]+3*s[1][rt]%mo*c%mo*c%mo+3*s[2][rt]%mo*c%mo+1ll*(r-l+1)*c%mo*c%mo*c%mo)%mo;
 24     s[2][rt]=(s[2][rt]+2*s[1][rt]%mo*c%mo+1ll*(r-l+1)*c%mo*c%mo)%mo;
 25     s[1][rt]=(s[1][rt]+1ll*(r-l+1)*c%mo)%mo;
 26     b1[rt]=(b1[rt]+c)%mo;
 27 }
 28 void c2(int rt,int l,int r,int c)
 29 {
 30     s[3][rt]=s[3][rt]*c%mo*c%mo*c%mo;
 31     s[2][rt]=s[2][rt]*c%mo*c%mo;
 32     s[1][rt]=s[1][rt]*c%mo;
 33     b1[rt]=b1[rt]*c%mo;
 34     b2[rt]=b2[rt]*c%mo;
 35 }
 36 void c3(int rt,int l,int r,int c)
 37 {
 38     s[3][rt]=1ll*c*c%mo*c%mo*(r-l+1)%mo;
 39     s[2][rt]=1ll*c*c%mo*(r-l+1)%mo;
 40     s[1][rt]=1ll*c*(r-l+1)%mo;
 41     b1[rt]=0;
 42     b2[rt]=1;
 43     b3[rt]=c;
 44 }
 45 void push(int rt,int l,int r)
 46 {
 47     int mid=l+r>>1;
 48     if (b3[rt])
 49     {
 50         c3(rt<<1,l,mid,b3[rt]);
 51         c3(rt<<1|1,mid+1,r,b3[rt]);
 52         b3[rt]=0;
 53     }
 54     if (b2[rt]!=1)
 55     {
 56         c2(rt<<1,l,mid,b2[rt]);
 57         c2(rt<<1|1,mid+1,r,b2[rt]);
 58         b2[rt]=1;
 59     }
 60     if (b1[rt])
 61     {
 62         c1(rt<<1,l,mid,b1[rt]);
 63         c1(rt<<1|1,mid+1,r,b1[rt]);
 64         b1[rt]=0;
 65     }
 66 }
 67 void m1(int rt,int l,int r,int x,int y,int z)
 68 {
 69     if (l>=x&&r<=y)
 70     {
 71         c1(rt,l,r,z);
 72         return;
 73     }
 74     push(rt,l,r);
 75     int mid=l+r>>1;
 76     if (x<=mid) m1(rt<<1,l,mid,x,y,z);
 77     if (y>mid) m1(rt<<1|1,mid+1,r,x,y,z);
 78     up(rt);
 79 }
 80 void m2(int rt,int l,int r,int x,int y,int z)
 81 {
 82     if (l>=x&&r<=y)
 83     {
 84         c2(rt,l,r,z);
 85         return;
 86     }
 87     push(rt,l,r);
 88     int mid=l+r>>1;
 89     if (x<=mid) m2(rt<<1,l,mid,x,y,z);
 90     if (y>mid) m2(rt<<1|1,mid+1,r,x,y,z);
 91     up(rt);
 92 }
 93 void m3(int rt,int l,int r,int x,int y,int z)
 94 {
 95     if (l>=x&&r<=y)
 96     {
 97         c3(rt,l,r,z);
 98         return;
 99     }
100     push(rt,l,r);
101     int mid=l+r>>1;
102     if (x<=mid) m3(rt<<1,l,mid,x,y,z);
103     if (y>mid) m3(rt<<1|1,mid+1,r,x,y,z);
104     up(rt);
105 }
106 int qq(int rt,int l,int r,int x,int y,int z)
107 {
108     if (l>=x&&r<=y) return s[z][rt];
109     push(rt,l,r);
110     int mid=l+r>>1,ret=0;
111     if (x<=mid) ret=ret+qq(rt<<1,l,mid,x,y,z);
112     if (y>mid) ret=ret+qq(rt<<1|1,mid+1,r,x,y,z);
113     return ret%mo;
114 }
115 int main()
116 {
117     int n,m;
118     while (1)
119     {
120         scanf("%d%d",&n,&m);
121         if (n==0&&m==0) break;
122         build(1,1,n);
123         for (int i=1;i<=m;i++)
124         {
125             int tp,l,r,x;
126             scanf("%d%d%d%d",&tp,&l,&r,&x);
127             if (tp==1) m1(1,1,n,l,r,x);
128             else if (tp==2) m2(1,1,n,l,r,x);
129             else if (tp==3) m3(1,1,n,l,r,x);
130             else printf("%d\n",qq(1,1,n,l,r,x)%mo);
131         }
132     }
133 }

3.可持久化线段树

#include
#pragma GCC optimize ("-Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int N=6e5+10;
int a[N],b[N],s[N],fr[N],aa[N],ans[N];
int ch[N*8][2],nd=1,tr[N*8];
int read()
{
    int x=0;
    char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}
void modify(int p1,int p2,int l,int r,int x)
{
    tr[p2]=tr[p1]+1;
    if (l==r) return;
    int mid=l+r>>1;
    if (x<=mid)
    {
        ch[p2][0]=++nd;
        ch[p2][1]=ch[p1][1];
        modify(ch[p1][0],ch[p2][0],l,mid,x);
    }else
    {
        ch[p2][1]=++nd;
        ch[p2][0]=ch[p1][0];
        modify(ch[p1][1],ch[p2][1],mid+1,r,x);
    }
}
int query(int rt,int l,int r,int x,int y)
{
    if (!rt) return 0;
    if (l>=x&&r<=y) return tr[rt];
    int mid=l+r>>1,ret=0;
    if (x<=mid&&ch[rt][0]) ret=ret+query(ch[rt][0],l,mid,x,y);
    if (y>mid&&ch[rt][1]) ret=ret+query(ch[rt][1],mid+1,r,x,y);
    return ret;
}
int main()
{
    int n,m;
    //scanf("%d%d",&n,&m);
    n=read();
    m=read();
    for (int i=1;i<=n;i++) a[i]=read(),b[i]=read(),s[i]=read();//scanf("%d%d%d",&a[i],&b[i],&s[i]);
    fr[0]=1;
    for (int i=1;i<=m;i++)
    {
        int x;
        //scanf("%d",&x);
        x=read();
        fr[i]=++nd;
        modify(fr[i-1],fr[i],1,N,x);
    }
    for (int i=1;i<=n;i++)
    {
        aa[i]=m+1;
        int l=s[i],r=m;
        while (l<=r)
        {
            int mid=l+r>>1;
            int py=query(fr[mid],1,N,a[i],b[i]);
            if (query(fr[mid],1,N,a[i],b[i])>=s[i])
            {
                aa[i]=mid;
                r=mid-1;
            }else l=mid+1;
        }
        ans[aa[i]]++;
    }
    for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
}

4.整体二分

 1 #include
 2 using namespace std;
 3 const int N=2e5+10;
 4 int tr[N],ans[N],a[N],b[N],c[N],d[N],id[N],a1[N],a2[N];
 5 void modify(int x,int y)
 6 {
 7     while (x<=N) tr[x]+=y,x=x+(x&(-x));
 8 }
 9 int query(int x)
10 {
11     int ret=0;
12     while (x) ret+=tr[x],x=x-(x&(-x));
13     return ret;
14 }
15 void solve(int l,int r,int x,int y)
16 {
17     if (l==r)
18     {
19         ans[l]+=(y-x+1);
20         return;
21     }
22     int mid=l+r>>1;
23     for (int i=l;i<=mid;i++) modify(d[i],1);
24     int c1=0,c2=0;
25     for (int i=x;i<=y;i++)
26     {
27         int tmp=query(b[id[i]])-query(a[id[i]]-1);
28         if (tmp>=c[id[i]]) a1[++c1]=id[i];else c[id[i]]-=tmp,a2[++c2]=id[i];
29     }
30     for (int i=l;i<=mid;i++) modify(d[i],-1);
31     for (int i=x;i<=x+c1-1;i++) id[i]=a1[i-x+1];
32     for (int i=x+c1;i<=y;i++) id[i]=a2[i-x-c1+1];
33     solve(l,mid,x,x+c1-1);
34     solve(mid+1,r,x+c1,y);
35 }
36 int main()
37 {
38     int n,m;
39     scanf("%d%d",&n,&m);
40     for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]),id[i]=i;
41     for (int i=1;i<=m;i++) scanf("%d",&d[i]);
42     solve(1,m+1,1,n);
43     for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
44 }