题目链接：

https://acm.ecnu.edu.cn/contest/173/problem/E/

 

思路：

区间修改，单点查询，本能地想到线段树。

本题有两种修改，如果只有一种修改，瞬间变成水题。那么两种修改该怎么维护数据呢？

以下说的“乘”“除”大多指操作1和操作2，请自行斟酌。考虑这样一种情况，如果对一个点连续地做几次乘操作，那么之后紧跟着的除操作只需要将乘操作的次数减少即可。

那么对这个点的操作将会变成连续的一段乘或者除。如果一段除操作之后出现了乘操作，那只能在一段除之后做一段乘操作了，因为执行了除之后minprime可能会变化。

所以最后对这个点的操作将会变成一段除操作跟着一段乘操作。

那么就可以利用线段树维护这样一段操作的除乘的个数了。线段树每个节点维护两个信息：除操作个数（dat[k].div），乘操作个数(dat[k].mul)。

同时子节点的操作一定是比父节点的操作先执行的，利用这一条性质我们就可以下传延迟标记（spread();）。父节点的除与子节点的乘抵消一部分，父节点的乘加到子节点的乘。

对于查询操作，就只需要统计一个点最后应该进行多少次除(int div;)乘（int mul;）。

最后进行连续的除和乘就可以计算出答案了。如何处理呢？涉及到了一点点数论。

 

除只需要从最小的素因子开始除起就可以了，参考代码：

ll cal_div(ll v,int t)//对v除t次
{
    if(t==0||v==1)
        return v;

    ll m=sqrt(v+0.5);

    for(ll i=2; i<=m; ++i)
       while(v%i==0)//如果整除，就一定是素因子
       {
           v/=i;
           --t;
           if(t==0||v==1)
               return v;
       }
    return 1;//如果还未除完所有素因子，那么有且只有一个素因子分布在sqrt(v)之后，除掉就变成1了。
}

 

对于乘，本题卡了一下快速幂，参考代码：

ll quick_pow(ll a,ll b)
{
    ll res=1;
    a%=mod;
    while(b)
    {
        if(b&1)
            res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}

int cal_mul(ll v,int t)
{
    if(t==0||v==1)
        return v;

    ll m=sqrt(v+0.5);

    int k=v;

    for(ll i=2; i<=m; ++i)
        if(v%i==0)
        {
            k=i;
            break;
        }
    v%=mod;
    k%=mod;

    return v*quick_pow(k,t)%mod;
}

整体框架：

1. 从线段树获取除乘次数。
2. 计算答案

 

完整代码：

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn=100000+5;
  4 const int mod=1000000007;
  5 typedef long long ll;
  6 
  7 struct Tree
  8 {
  9     int mul,div;
 10 };
 11 
 12 Tree dat[maxn*4];
 13 int a[maxn];
 14 
 15 ll cal_div(ll v,int t)
 16 {
 17     if(t==0||v==1)
 18         return v;
 19 
 20     ll m=sqrt(v+0.5);
 21 
 22     for(ll i=2; i<=m; ++i)
 23         while(v%i==0)
 24         {
 25             v/=i;
 26             --t;
 27             if(t==0||v==1)
 28                 return v;
 29         }
 30     return 1;
 31 }
 32 
 33 ll quick_pow(ll a,ll b)
 34 {
 35     ll res=1;
 36     a%=mod;
 37     while(b)
 38     {
 39         if(b&1)
 40             res=res*a%mod;
 41         b>>=1;
 42         a=a*a%mod;
 43     }
 44     return res;
 45 }
 46 
 47 int cal_mul(ll v,int t)
 48 {
 49     if(t==0||v==1)
 50         return v;
 51 
 52     ll m=sqrt(v+0.5);
 53 
 54     int k=v;
 55 
 56     for(ll i=2; i<=m; ++i)
 57         if(v%i==0)
 58         {
 59             k=i;
 60             break;
 61         }
 62     v%=mod;
 63     k%=mod;
 64 
 65     return v*quick_pow(k,t)%mod;
 66 }
 67 
 68 void spread(int k,int l,int r)
 69 {
 70     if(dat[k].div==0&&dat[k].mul==0)
 71         return;
 72     int lc=2*k+1;
 73     int rc=2*k+2;
 74 
 75     int t=min(dat[k].div,dat[lc].mul);
 76     dat[lc].mul-=t;
 77     dat[lc].div+=dat[k].div-t;
 78     dat[lc].mul+=dat[k].mul;
 79 
 80     t=min(dat[k].div,dat[rc].mul);
 81     dat[rc].mul-=t;
 82     dat[rc].div+=dat[k].div-t;
 83     dat[rc].mul+=dat[k].mul;
 84 
 85     dat[k].div=dat[k].mul=0;
 86 }
 87 
 88 void change1(int x,int y,int k,int l,int r)//mul
 89 {
 90     int m=(l+r)>>1;
 91     int lc=2*k+1;
 92     int rc=2*k+2;
 93 
 94     if(x<=l&&y>=r)
 95     {
 96         ++dat[k].mul;
 97         return;
 98     }
 99     spread(k,l,r);
100     if(x<m)
101         change1(x,y,lc,l,m);
102     if(y>m)
103         change1(x,y,rc,m,r);
104 }
105 
106 void change2(int x,int y,int k,int l,int r)//div
107 {
108     if(x<=l&&y>=r)
109     {
110         if(dat[k].mul)
111             --dat[k].mul;
112         else ++dat[k].div;
113         return;
114     }
115     spread(k,l,r);
116     int m=(l+r)>>1;
117     int lc=2*k+1;
118     int rc=2*k+2;
119 
120     if(x<m)
121         change2(x,y,lc,l,m);
122     if(y>m)
123         change2(x,y,rc,m,r);
124 }
125 
126 void query(int &div,int &mul,int pos,int k,int l,int r)
127 {
128     if(r-l==1)
129     {
130         int t=min(mul,dat[k].div);
131         mul-=t;
132         div+=dat[k].div-t;
133         mul+=dat[k].mul;
134         return;
135     }
136 
137     int m=(l+r)>>1;
138     int lc=2*k+1;
139     int rc=2*k+2;
140 
141     if(pos<m)
142         query(div,mul,pos,lc,l,m);
143     else
144         query(div,mul,pos,rc,m,r);
145 
146     int t=min(mul,dat[k].div);
147     mul-=t;
148     div+=dat[k].div-t;
149     mul+=dat[k].mul;
150 }
151 
152 int main()
153 {
154     int n,m;
155     scanf("%d%d",&n,&m);
156     for(int i=0; i<n; ++i)
157         scanf("%d",a+i);
158 
159     int op,x,y;
160 
161     while(m--)
162     {
163         scanf("%d",&op);
164         if(op==3)
165         {
166             scanf("%d",&x);
167             int div=0;
168             int mul=0;
169             query(div,mul,x-1,0,0,n);//传引用计算div,mul
170 
171             ll ans=cal_div(a[x-1],div);//除
172             ans=cal_mul(ans,mul);//乘
173 
174             printf("%lld\n",ans%mod);
175         }
176         else
177         {
178             scanf("%d%d",&x,&y);
179             if(op==1)
180                 change1(x-1,y,0,0,n);//乘
181             else
182                 change2(x-1,y,0,0,n);//除
183         }
184     }
185     return 0;
186 }

AC代码