2020暑假集训做题记录—

2020暑假集训做题记录——数据结构

题目质量很赞。这么多道数据结构，却不全是很裸的板子，并且带有卡常题

A：模拟

WA了好几发，贼蠢的题，非负整数是个坑

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define N1 2000050
 5 using namespace std;
 6 
 7 int T,n;
 8 char str[N1];
 9 
10 int main()
11 {
12     scanf("%d",&T);
13     while(T--)
14     {
15         scanf("%d",&n);
16         if(!n){ puts("0"); continue; }
17         scanf("%s",str+1);
18         int cnt=0,tot=0;
19         for(int i=1;i<=n;i++)
20         {
21             if(str[i]=='('){
22                 cnt++;
23             }else{
24                 if(cnt>0) cnt--, tot+=2;
25             }
26         }
27         printf("%d
",n-tot);
28     }
29     return 0;
30 }

View Code

B：图论

a[i]向i连边，由于每个点入度都是1，发现图中每个连通块都是基环树，并且只能是环向外有出边。所以连通块个数就是答案

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define N1 1000050
 5 #define M1 N1*2
 6 using namespace std;
 7 
 8 struct Edge{
 9 int to[M1],nxt[M1],head[N1],cte;
10 void ae(int u,int v)
11 {cte++; to[cte]=v; nxt[cte]=head[u]; head[u]=cte; }
12 }e;
13 int T,n;
14 int a[N1],used[N1];
15 void dfs(int u)
16 {
17     used[u]=1;
18     for(int j=e.head[u];j;j=e.nxt[j])
19     {
20         int v=e.to[j]; if(used[v]) continue;
21         dfs(v);
22     }
23 }
24 
25 int main()
26 {
27     scanf("%d",&n);
28     int ans=0;
29     for(int i=1;i<=n;i++) 
30     {
31         scanf("%d",&a[i]);
32         if(i!=a[i]) e.ae(a[i],i), e.ae(i,a[i]);
33     }
34     for(int i=1;i<=n;i++) 
35     {
36         if(!used[i]) dfs(i), ans++;
37     }
38     printf("%d
",ans);
39     return 0;
40 }

View Code

C：树状数组

设s[i]是前缀和。考虑暴力做法：枚举i,j(i>j>=0)，统计满足s[i]-s[j]<=k(i-j)的i,j对数就行了。正解就挪一下式子，把i,j移到两侧，得到s[i]-ki<=s[j]-kj。所以预处理出所有s[i]-ki，离散一下用树状数组维护就行。不想离散就动态开点线段树2333。统计出来以后gcd一下就行。注意离散化的时候从第2位开始赋离散后的值

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define N1 200010
 5 #define M1 N1*2
 6 #define ll long long 
 7 using namespace std;
 8 
 9 ll gcd(ll a,ll b)
10 {
11     if(!b) return a;
12     return gcd(b,a%b);
13 }
14 int n,m; ll K;
15 int a[N1],pos[N1];
16 ll sa[N1];
17 
18 struct Bit{
19 ll sum[N1];
20 void upd(int x,int w){
21     for(int i=x;i<=m;i+=i&(-i)) sum[i]+=w;
22 }
23 ll query(int x)
24 {
25     ll ans=0;
26     for(int i=x;i>0;i-=i&(-i)) ans+=sum[i];
27     return ans;
28 }
29 }s;
30 struct node{
31 int id; ll w;
32 }sp[N1];
33 int cmp(node a1,node a2)
34 {
35     if(a1.w!=a2.w) return a1.w<a2.w;
36     return a1.id<a2.id; 
37 }
38 
39 int main()
40 {
41     freopen("a.txt","r",stdin);
42     scanf("%d%lld",&n,&K);
43     for(int i=1;i<=n;i++) scanf("%d",&a[i]), sa[i]=sa[i-1]+a[i];
44     for(int i=1;i<=n;i++) sp[i].w=sa[i]-K*i, sp[i].id=i;
45     sp[n+1]=(node){0,0};
46     sort(sp+1,sp+n+2,cmp); 
47     m=1, pos[sp[1].id]=m;
48     for(int i=2;i<=n+1;i++)
49     {
50         if(sp[i-1].w!=sp[i].w) m++;
51         pos[sp[i].id]=m;
52     }
53     s.upd(pos[n],1); ll ans=0;
54     for(int i=n-1;i>=0;i--)
55     {
56         ans+=s.query(pos[i]);
57         s.upd(pos[i],1);
58     }
59     // printf("%lld
",ans);
60     ll t1=ans,t2=1ll*(n+1)*n/2, g=gcd(t1,t2);
61     printf("%lld/%lld
",t1/g,t2/g);
62     return 0;
63 }

View Code

D：线段树

很普通的线段树题，我还卡了将近40min，菜爆了

线段树维护一下？记录f[rt][0]表示左侧余下的)数量，f[rt][1]表示右侧余下(的数量，这两个变量用于判断括号序列是否合法，它们向上合并的式子并不难。再考虑最大嵌套怎么求，考虑暴力做法，打差分，把(当成+1，)当成-1，求一次前缀和，因为保证括号序列合法，求完以后序列元素的最大值就是最大嵌套层数。把这个做法扔线段树里就可以动态了！当前区间的答案就是max(左区间答案,左区间前缀和+右区间答案)。

左侧多余的）和右侧多余的（不必特殊讨论，因为它们迟早得被匹配上，假设左右都给补全就行。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define N1 1000005
 5 #define M1 N1*4
 6 #define ll long long 
 7 using namespace std;
 8 
 9 struct SEG{
10 int f[M1][2],sum[M1],ma[M1];
11 #define ls rt<<1
12 #define rs rt<<1|1
13 void pushup(int rt)
14 {
15     f[rt][0]=f[ls][0]+max(f[rs][0]-f[ls][1],0); //left remain ) -1
16     f[rt][1]=f[rs][1]+max(f[ls][1]-f[rs][0],0); //right remain ( 1
17     sum[rt]=sum[ls]+sum[rs];
18     ma[rt]=max(ma[ls],sum[ls]+ma[rs]);
19 }
20 void upd(int x,int l,int r,int rt,int w)
21 {
22     if(l==r){
23         if(w==-1) f[rt][0]=1, f[rt][1]=0;  // )
24         if(w==0)  f[rt][0]=0, f[rt][1]=0;  // *
25         if(w==1)  f[rt][0]=0, f[rt][1]=1;  // (
26         sum[rt]=w, ma[rt]=w; return; 
27     }
28     int mid=(l+r)>>1;
29     if(x<=mid) upd(x,l,mid,ls,w);
30     else upd(x,mid+1,r,rs,w);
31     pushup(rt);
32 }
33 #undef ls
34 #undef rs
35 }s;
36 
37 int check()
38 {
39     if(s.sum[1] || s.f[1][0] || s.f[1][1]) return -1;
40     return s.ma[1];
41 }
42 
43 int n,ma,mi,m;
44 char comd[N1],str[N1];
45 
46 int main()
47 {
48     freopen("a.txt","r",stdin);
49     scanf("%d",&n); 
50     if(!n) return 0;
51     scanf("%s",comd+1);
52     int tmp=0,pos,ans;
53     ma=0,mi=0;
54     for(int i=1;i<=n;i++) 
55         if(comd[i]=='R') tmp++, ma=max(ma,tmp);
56         else if(comd[i]=='L') tmp--, mi=min(mi,tmp);
57     pos=1-mi; m=ma-mi+1;
58     for(int i=1;i<=n;i++)
59     {
60         if(comd[i]=='L') pos--;
61         else if(comd[i]=='R') pos++;
62         else if(comd[i]=='(') s.upd(pos,1,m,1,1);
63         else if(comd[i]==')') s.upd(pos,1,m,1,-1);
64         else s.upd(pos,1,m,1,0);
65         ans=check();
66         printf("%d ",ans);
67     }
68     puts("");
69     return 0;
70 }

View Code

E：二维RMQ维护gcd

板子题，看到n=500以为$O(n^{3}+n^{2}log^{2}n)$能卡过，结果一直T，咋卡常也没用，数据很强。会寝室路上突然想到RMQ可以拓展到二维，枚举每个点再二分答案就行了，可以优化成$O(n^{2}logn+n^{2}log^{2}n)$。回去写了一发，终于过了

 1 #include <ctime>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define N1 505
 6 #define ll long long 
 7 using namespace std;
 8 
 9 inline int gcd(int x,int y)
10 {
11     if(!y) return x;
12     return gcd(y,x%y);
13 }
14 template <typename _T> void read(_T &ret)
15 {
16     ret=0; _T fh=1; char c=getchar();
17     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
18     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
19     ret=ret*fh;
20 }
21 
22 int n,m,ma;
23 int a[N1][N1],lg[N1];
24 int g[N1][N1][12];
25 int qg(int x,int y,int len)
26 {
27     return gcd( gcd( g[x][y][lg[len]],g[x][y+len-1-(1<<lg[len])+1][lg[len]]) , gcd(g[x+len-1-(1<<lg[len])+1][y][lg[len]], g[x+len-1-(1<<lg[len])+1][y+len-1-(1<<lg[len])+1][lg[len]]) ) ;
28 }
29 
30 int main()
31 {
32     scanf("%d%d",&n,&m);
33     clock_t st,ed;
34     st=clock();
35     for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(a[i][j]);
36     ma=max(n,m); lg[1]=0;
37     int ans=0,num=0;
38     for(int i=2;i<=ma;i++) lg[i]=lg[i>>1]+1;
39     for(int i=1;i<=n;i++) 
40     {
41         for(int j=1;j<=m;j++) g[i][j][0]=a[i][j];
42     }
43     for(int k=1;k<=lg[ma];k++)
44     for(int i=1;i+(1<<k)-1<=n;i++) 
45     {
46         for(int j=1;j+(1<<k)-1<=m;j++) 
47         {
48             g[i][j][k]=gcd( gcd(g[i][j][k-1],g[i][j+(1<<(k-1))][k-1]) , gcd(g[i+(1<<(k-1))][j][k-1],g[i+(1<<(k-1))][j+(1<<(k-1))][k-1]) );
49         }
50     }
51     int tmp,l,r,mid,k;
52     for(int i=1;i<=n;i++)
53     for(int j=1;j<=m;j++)
54     {
55         k=0, l=1, r=min(min(m-j,j-1),min(n-i,i-1));
56         while(l<=r)
57         {
58             mid=(l+r)>>1; tmp=qg(i-mid,j-mid,2*mid+1);
59             if(tmp%a[i][j]==0) k=mid, l=mid+1;
60             else r=mid-1;
61         }
62         if((2*k+1)*(2*k+1)>ans) ans=(2*k+1)*(2*k+1), num=1;
63         else if((2*k+1)*(2*k+1)==ans) num++;
64     }
65     printf("%d
%d
",ans,num);
66     return 0;
67 }

View Code

F：贪心+set 好题

考虑一条链的情况，搞个set记录现在有哪些佣兵可用，再用田忌赛马策略。对于每个任务，找后继（第一个比需要的能力值大的忍者），如果没有后继，就把最次的佣兵安排上。

环怎么办。。。卡了1h多想不出弃疗看题解去了

看了byaidu学长的题解，原来可以断环？？！

如果佣兵和任务是一一映射，那么答案唯一，特判一下就好

对于其他的情况，会有的任务有很多佣兵，那么它之后的几个任务的佣兵都可以由它提供剩余的佣兵，它们之间可以互相影响。那么可能相互影响的任务一定是环上连续的一段。如果这一段的任务数量>1，那么最后一个肯定是空任务结尾，且它和前面的任务都不能影响后面的任务。整个序列都是一段的情况依然成立

有了上面的结论，把环给转一下，就可以化成链，舍去尾对头的影响了！

用链表实现任务的添加和删除，用set找后继

另外vector是真不快

  1 #include <set>
  2 #include <ctime>
  3 #include <vector>
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <algorithm>
  7 #define N1 500005
  8 #define ll long long 
  9 #define its set<int>::iterator
 10 #define itv vector<int>::iterator
 11 using namespace std;
 12 
 13 template <typename _T> void read(_T &ret)
 14 {
 15     ret=0; _T fh=1; char c=getchar();
 16     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
 17     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
 18     ret=ret*fh;
 19 }
 20 int n;
 21 int id[N1],a[N1],b[N1],num[N1];
 22 struct node{
 23     int l,r;
 24 }lst[N1];
 25 struct Edge{
 26 int to[N1],nxt[N1],head[N1],cte;
 27 void ae(int u,int v)
 28 { cte++; to[cte]=v, nxt[cte]=head[u], head[u]=cte; }
 29 }e;
 30 void pre_lst()
 31 {
 32     lst[1].l=n, lst[1].r=2;
 33     for(int i=2;i<n;i++) lst[i].l=i-1,lst[i].r=i+1;
 34     lst[n].l=n-1, lst[n].r=1;
 35 }
 36 int del(int i)
 37 {
 38     lst[lst[i].l].r=lst[i].r;
 39     lst[lst[i].r].l=lst[i].l;
 40     return lst[i].r;
 41 }
 42 int find_st()
 43 {
 44     pre_lst();
 45     int tot=n,i=1,res,st;
 46     while(tot)
 47     {
 48         if(!num[i]){ i=lst[i].r; continue; }
 49         res=num[i];
 50         while(res)
 51         {
 52             i=del(i); res--; tot--; 
 53             if(res==0) break;
 54             res+=num[i];
 55         }
 56     }
 57     if(!tot) st=(i==n?1:i+1); else st=i;
 58     return st;
 59 }
 60 set<int>s;
 61 vector<int>mer[N1];
 62 int solve(int i)
 63 {
 64     pre_lst();
 65     int tot=n,j,ans=0;its k;
 66     for(;tot;)
 67     {
 68         // if(!num[i]){ i=lst[i].r; continue; }
 69         for(j=0;j<mer[i].size();j++) s.insert(b[mer[i][j]]);
 70         // for(j=e.head[i];j;j=e.nxt[j]) s.insert(b[e.to[j]]);
 71         if(s.empty()){ i=lst[i].r; continue; }
 72         k=s.upper_bound(a[i]);
 73         if(k==s.end()){
 74             k=s.begin(); s.erase(*k);
 75         }else{
 76             s.erase(*k); ans++;
 77         }
 78         i=del(i), tot--; 
 79     }
 80     return ans;
 81 }
 82 
 83 int main()
 84 {
 85     // freopen("f.txt","r",stdin);
 86     // freopen("a.in","r",stdin);
 87     // freopen("f.out","w",stdout);
 88     clock_t sta,ed,tmp;
 89     sta=clock();
 90     scanf("%d",&n);
 91     for(int i=1;i<=n;i++) read(id[i]), num[id[i]]++;
 92     for(int i=1;i<=n;i++) mer[id[i]].emplace_back(i);
 93     // for(int i=1;i<=n;i++) read(id[i]), num[id[i]]++, e.ae(id[i],i);
 94     for(int i=1;i<=n;i++) read(a[i]); //任务
 95     for(int i=1;i<=n;i++) read(b[i]); //佣兵
 96     int flag=1; int ans=0;
 97     for(int i=1;i<=n;i++) if(num[i]!=1){ flag=0; break; }
 98     if(flag)
 99     {
100         for(int i=1;i<=n;i++)
101         {
102             if(b[i]>a[id[i]]) ans++;
103         }
104         printf("%d
",ans); 
105         return 0;
106     }
107     int st=find_st();
108     ans=solve(st);
109     printf("%d
",ans);
110     // ed=clock(); printf("%.7lf s
",(double)(ed-sta)/CLOCKS_PER_SEC);
111     return 0;
112 }

View Code

G：线段树合并+离散化

线段树合并板子题，但此题很毒瘤似乎卡空间，于是乎需要离散，把dis[x]和dis[x]+L一起离散2333

线段树合并又又又又又又又又又又tnnd打错了，调了30minWA了2发，再打错我就是sb！

  1 #include <set>
  2 #include <ctime>
  3 #include <vector>
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <algorithm>
  7 #define N1 400005
  8 #define ll long long 
  9 #define its set<int>::iterator
 10 #define itv vector<int>::iterator
 11 using namespace std;
 12 
 13 template <typename _T> void read(_T &ret)
 14 {
 15     ret=0; _T fh=1; char c=getchar();
 16     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
 17     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
 18     ret=ret*fh;
 19 }
 20 struct Edge{
 21 int to[N1],nxt[N1],head[N1],cte; ll val[N1];
 22 void ae(int u,int v,ll w)
 23 {
 24     cte++; to[cte]=v, nxt[cte]=head[u];
 25     head[u]=cte, val[cte]=w;
 26 }
 27 }e;
 28 struct SEG{; //2N*log*2
 29 int sum[N1*40],ls[N1*40],rs[N1*40],root[N1],cnt;
 30 void pushup(int rt){ sum[rt]=sum[ls[rt]]+sum[rs[rt]]; }
 31 void upd(int x,int l,int r,int &rt,int w)
 32 {
 33     if(!rt) rt=++cnt;
 34     // if(cnt>=N1*40) puts("-1");
 35     if(l==r){ sum[rt]+=w; return; }
 36     int mid=(l+r)>>1;
 37     if(x<=mid) upd(x,l,mid,ls[rt],w);
 38     else upd(x,mid+1,r,rs[rt],w);
 39     pushup(rt);
 40 }
 41 int mrg(int r1,int r2)
 42 {
 43     if(!r1||!r2) return r1+r2;
 44     int rt=++cnt;
 45     ls[rt]=mrg(ls[r1],ls[r2]);
 46     rs[rt]=mrg(rs[r1],rs[r2]);
 47     sum[rt]=sum[r1]+sum[r2];
 48     return rt;
 49 }
 50 int query(int L,int R,int l,int r,int rt)
 51 {
 52     if(L<=l&&r<=R) return sum[rt];
 53     int mid=(l+r)>>1,ans=0;
 54     if(L<=mid) ans+=query(L,R,l,mid,ls[rt]);
 55     if(R>mid) ans+=query(L,R,mid+1,r,rs[rt]);
 56     return ans;
 57 }
 58 }s;
 59 int n,m; ll L;
 60 int dis[N1],disl[N1],ans[N1];
 61 struct node{ int id,p; ll w; }bar[N1];
 62 int cmp(node s1,node s2)
 63 { 
 64     if(s1.w!=s2.w) return s1.w<s2.w; 
 65     if(s1.p!=s2.p) return s1.p<s2.p; 
 66     return s1.id<s2.id; 
 67 }
 68 
 69 void dfs1(int u)
 70 {
 71     int j,v;
 72     bar[u].id=u; bar[u+n].id=u; bar[u].p=0; bar[u+n].p=1;
 73     bar[u+n].w=bar[u].w+L;
 74     for(j=e.head[u];j;j=e.nxt[j])
 75     {
 76         v=e.to[j]; 
 77         bar[v].w=bar[u].w+e.val[j]; 
 78         // dis[v]=dis[u]+e.val[j];
 79         dfs1(v);
 80     }
 81 }
 82 void dfs2(int u)
 83 {
 84     int j,v;
 85     s.upd(dis[u],1,m,s.root[u],1);
 86     for(j=e.head[u];j;j=e.nxt[j])
 87     {
 88         v=e.to[j]; 
 89         dfs2(v);
 90         s.root[u]=s.mrg(s.root[u],s.root[v]);
 91     }
 92     if(u==1)
 93         n=n;
 94     ans[u]=s.query(1,disl[u],1,m,s.root[u]);
 95 }
 96 int main()
 97 {
 98     read(n); read(L);
 99     int x; ll y;
100     for(int i=2;i<=n;i++) read(x), read(y), e.ae(x,i,y);
101     dfs1(1);
102     sort(bar+1,bar+2*n+1,cmp); 
103     bar[0].w=-1;
104     for(int i=1;i<=2*n;i++) 
105     {
106         if(bar[i].w!=bar[i-1].w) m++;
107         if(!bar[i].p) dis[bar[i].id]=m;
108         else disl[bar[i].id]=m;
109     }
110     dfs2(1);
111     for(int i=1;i<=n;i++) printf("%d
",ans[i]);
112     return 0;
113 }

View Code

H：分块

原来想了个拆询问+主席树的log方做法，写了一下发现是假的qwq。

索性暴力分块。不过复习了分块也不错

卡常卡半天我好难，实测块大小为250跑的最快。

 1 #include <ctime>
 2 #include <vector>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #define N1 100005
 7 #define M1 N1*4
 8 #define ll long long 
 9 using namespace std;
10 
11 template <typename _T> void read(_T &ret)
12 {
13     ret=0; _T fh=1; char c=getchar();
14     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
15     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
16     ret=ret*fh;
17 }
18 const ll sq=250;
19 
20 int getid(int x){ return (x-1)/sq+1; }
21 int n,K,m;
22 int a[N1],tag[N1/sq+5],sum[N1/sq+5][N1];
23 void pushdown(int id)
24 {
25     if(!tag[id]) return; 
26     for(int i=(id-1)*sq+1;i<=id*sq;i++)
27     {
28         sum[id][a[i]]--;
29         (a[i]+=tag[id])%=K;
30         sum[id][a[i]]++;
31     }
32     tag[id]=0;
33 }
34 
35 int main()
36 {
37     // freopen("h.txt","r",stdin);
38     freopen("h.in","r",stdin);
39     freopen("h0.out","w",stdout);
40     clock_t sta,ed,tmp;
41     sta=clock();
42     read(n); read(K);
43     for(int i=1;i<=n;i++) read(a[i]), a[i]=(a[i]%K+K)%K;
44     read(m);
45     int l,r,c,d,ans,lid,rid;
46     for(int i=1;i<=n;i++)
47     {
48         sum[getid(i)][a[i]]++;
49     }
50     for(int k=1;k<=m;k++)
51     {
52         read(l); read(r); read(c); read(d); ans=0;
53         c=(c%K+K)%K; d=(d%K+K)%K; 
54         lid=getid(l); rid=getid(r); 
55         pushdown(lid); pushdown(rid);
56         if(lid==rid)
57         {
58             for(int i=l;i<=r;i++)
59             {
60                 if(a[i]==c) ans++;
61                 sum[lid][a[i]]--; (a[i]+=d)%=K; sum[lid][a[i]]++;
62             }
63         }else{
64             for(int i=l;i<=lid*sq;i++) 
65             {
66                 if(a[i]==c) ans++;
67                 sum[lid][a[i]]--; (a[i]+=d)%=K; sum[lid][a[i]]++;
68             }
69             for(int i=lid+1;i<=rid-1;i++) 
70             {
71                 ans+=sum[i][(c-tag[i]+K)%K];
72                 (tag[i]+=d)%=K;
73             }
74             for(int i=(rid-1)*sq+1;i<=r;i++) 
75             {
76                 if(a[i]==c) ans++;
77                 sum[rid][a[i]]--; (a[i]+=d)%=K; sum[rid][a[i]]++;
78             }
79         }
80         printf("%d
",ans);
81     }
82     // ed=clock(); printf("%.7lf s
",(double)(ed-sta)/CLOCKS_PER_SEC);
83     return 0;
84 }

View Code

I：种类并查集

竟然不会了我太菜了，复习一波并查集拓展做法√

种类并查集板子题，和NOI2001 食物链一个做法。开三倍的n记录点和点之间的关系

并查集不能维护删边，所以我们倒着遍历询问变成了加边。注意删除同一个操作时需要在第一次（倒着看就是最后一次）删除的时候加边！

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N1=100005;
 6 const int M1=1000005;
 7 
 8 template <typename _T> void read(_T &ret)
 9 {
10     ret=0; _T fh=1; char c=getchar();
11     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
12     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
13     ret=ret*fh;
14 }
15 
16 int n,K,m;
17 int fa[N1*3];
18 // vector<int>son[N1];
19 int used[M1],prt[M1],cnt;
20 struct comd{ int p,x,y; }des[M1],ques[M1];
21 
22 int findfa(int x)
23 {
24     int y=x,t;
25     while(fa[y]!=y) y=fa[y];
26     while(fa[x]!=y){ t=fa[x], fa[x]=y, x=t; }
27     return y;
28 }
29 int mrg(int x,int y)
30 {
31     int fx=findfa(x), fy=findfa(y);
32     if(fx==fy) return fx; 
33     fa[fy]=fx;
34     return fx;
35 }
36 int check(int x,int y)
37 {
38     if(findfa(x)==findfa(y)) return 1;
39     return 0;
40 }
41 
42 
43 int main()
44 {
45     freopen("a.in","r",stdin);
46     scanf("%d%d%d",&n,&K,&m);
47     char str[10];
48     for(int i=1;i<=K;i++) read(des[i].p), read(des[i].x), read(des[i].y);
49     for(int i=1;i<=m;i++)
50     {
51         scanf("%s",str);
52         if(str[0]=='q'){
53             ques[i].p=1; read(ques[i].x); read(ques[i].y);
54         }else{
55             ques[i].p=2; read(ques[i].x); 
56             if(!used[ques[i].x]) used[ques[i].x]=i;
57         }
58     }
59     for(int i=1;i<=3*n;i++) fa[i]=i;
60     int p,x,y,ans;
61     for(int i=1;i<=K;i++)
62     {
63         if(used[i]) continue;
64         p=des[i].p, x=des[i].x, y=des[i].y;
65         if(p==1){
66             mrg(x,y); mrg(x+n,y+n); mrg(x+2*n,y+2*n);
67         }else{
68             mrg(x+n,y); mrg(x+2*n,y+n); mrg(x,y+2*n);
69         }
70     }
71     for(int j=m,i;j>=1;j--)
72     {
73         if(ques[j].p==1){
74             x=ques[j].x, y=ques[j].y;
75             if(check(x,y)&&check(x+n,y+n)&&check(x+2*n,y+2*n)) ans=0;
76             else if(check(x+n,y)&&check(x+2*n,y+n)&&check(x,y+2*n)) ans=1;
77             else if(check(y+n,x)&&check(y+2*n,x+n)&&check(y,x+2*n)) ans=2;
78             else ans=3;
79             prt[++cnt]=ans;
80             // printf("%d
",ans);
81         }else{       
82             i=ques[j].x;
83             if(used[i]!=j) continue; 
84             p=des[i].p, x=des[i].x, y=des[i].y;
85             if(p==1){
86                 mrg(x,y); mrg(x+n,y+n); mrg(x+2*n,y+2*n);
87             }else{
88                 mrg(x+n,y); mrg(x+2*n,y+n); mrg(x,y+2*n);
89             }
90         }
91     }
92     for(int i=cnt;i>=1;i--) printf("%d
",prt[i]);
93     return 0;
94 }

View Code

J：点分治+01Trie

把点分治给忘了我太弱了555，复习一波点分治板子√

原来想了一个01Trie启发式合并，写了一下发现又是假做法。。

统计链性质的问题多半都能用点分治搞呢

对于每个点的点分树，暴力上01trie求解答案就行了= =

怎么统计？按位分0/1讨论，r的答案减掉l-1的答案，注意l-1可能小于0

转化成如下问题：

已知数列$a$和数列$b$，要求有多少对$ai^bjle maxn$

对$a$建成$01trie$，一次遍历$b$中每个元素求答案

按位从高到低讨论，也就是在$01trie$上走

如果$maxn$某一位是1：

$bj$是0，$ai$这一位填0一定成立，答案加上$sum[ch(x,0)]$。填1不一定成立，需要看后面的位，走向1儿子

$bj$是1，$ai$这一位填1一定成立，答案加上$sum[ch(x,1)]$。填0不一定成立，需要看后面的位，走向0儿子

如果$maxn$某一位是0：

$bj$是0，$ai$这一位只能填0而且需要看后面的位，走向0儿子

$bj$是1，$ai$这一位只能填1而且需要看后面的位，走向1儿子

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define ll long long
  5 using namespace std;
  6 const int maxn=29;
  7 const int N1=100005;
  8 const int M1=3100005;
  9 template <typename _T> void read(_T &ret)
 10 {
 11     ret=0; _T fh=1; char c=getchar();
 12     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
 13     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
 14     ret=ret*fh;
 15 }
 16 
 17 int n,l,r,de;
 18 struct Edge{
 19 int to[N1*2],nxt[N1*2],head[N1],cte;
 20 void ae(int u,int v)
 21 {cte++; to[cte]=v, nxt[cte]=head[u], head[u]=cte; }
 22 }e;
 23 struct Trie{
 24 int sum[M1],ch[M1][2],cnt;
 25 void clr()
 26 {
 27     for(int i=1;i<=cnt;i++) sum[i]=ch[i][0]=ch[i][1]=0;
 28     cnt=1;
 29 }
 30 void upd(int w)
 31 {
 32     int p,x=1;
 33     for(int i=maxn;i>=0;i--)
 34     {
 35         p=(w>>i)&1; 
 36         if(!ch[x][p]) ch[x][p]=++cnt; 
 37         x=ch[x][p]; sum[x]++;
 38     }
 39 }
 40 int query(int w,int m)
 41 {
 42     int ans=0,x=1;
 43     if(m<0) return 0;
 44     for(int i=maxn;i>=0;i--)
 45     {
 46         if((m>>i)&1){
 47             if((w>>i)&1) ans+=sum[ch[x][1]], x=ch[x][0]; // w 1  r 1
 48             else ans+=sum[ch[x][0]], x=ch[x][1]; // w 0  r 1
 49             if(!i) ans+=sum[x];
 50         }else{
 51             if((w>>i)&1) x=ch[x][1]; // w 1  r 0
 52             else x=ch[x][0]; // w 0  r 0
 53             if(!i) ans+=sum[x];
 54         }
 55     }
 56     return ans;
 57 }
 58 }t;
 59 
 60 int used[N1],sz[N1],ms[N1],tsz,G;
 61 void gra(int u,int dad)
 62 {
 63     sz[u]=1; ms[u]=0;
 64     for(int j=e.head[u];j;j=e.nxt[j])
 65     {
 66         int v=e.to[j];
 67         if(v==dad||used[v]) continue; 
 68         gra(v,u); sz[u]+=sz[v];
 69         ms[u]=max(ms[u],sz[v]);
 70     }
 71     ms[u]=max(ms[u],tsz-sz[u]);
 72     if(ms[u]<ms[G]) G=u;
 73 }
 74 int a[N1],sa0[N1],sa1[N1];
 75 void dfs0(int u,int dad)
 76 {
 77     for(int j=e.head[u];j;j=e.nxt[j])
 78     {
 79         int v=e.to[j]; if(v==dad||used[v]) continue; 
 80         sa0[v]=sa0[u]^a[v]; sa1[v]=sa1[u]^a[v];
 81         dfs0(v,u);
 82     }
 83 }
 84 ll dfs1(int u,int dad) //calc
 85 {
 86     ll ans=t.query(sa1[u],r);
 87     ans-=t.query(sa1[u],l-1);
 88     for(int j=e.head[u];j;j=e.nxt[j])
 89     {
 90         int v=e.to[j];
 91         if(v==dad||used[v]) continue; 
 92         ans+=dfs1(v,u);
 93     }
 94     return ans;
 95 }
 96 void dfs2(int u,int dad) //update in trie
 97 {
 98     t.upd(sa0[u]);
 99     for(int j=e.head[u];j;j=e.nxt[j])
100     {
101         int v=e.to[j];
102         if(v==dad||used[v]) continue; 
103         dfs2(v,u);
104     }
105 }
106 ll calc(int u)
107 {
108     sa0[u]=a[u]; sa1[u]=0; dfs0(u,-1);
109     t.upd(sa0[u]);
110     ll ans=0;
111     for(int j=e.head[u];j;j=e.nxt[j])
112     {
113         int v=e.to[j]; if(used[v]) continue; 
114         ans+=dfs1(v,u); 
115         dfs2(v,u);
116     }
117     t.clr();
118     return ans;
119 }
120 ll main_dfs(int u)
121 {
122     ll ans=0;
123     used[u]=1; ans+=calc(u);
124     for(int j=e.head[u];j;j=e.nxt[j])
125     {
126         int v=e.to[j]; if(used[v]) continue; 
127         G=0; tsz=sz[v]; gra(v,u);
128         ans+=main_dfs(G);
129     }
130     return ans;
131 }
132 
133 int main()
134 {
135     freopen("a.in","r",stdin);
136     int x,y;
137     scanf("%d%d%d",&n,&l,&r);
138     for(int i=1;i<=n;i++) read(a[i]);
139     for(int i=1;i<n;i++) read(x), read(y), e.ae(x,y), e.ae(y,x);
140     ms[0]=tsz=n; gra(1,-1); gra(G,-1);
141     t.clr();
142     ll ans=main_dfs(G);
143     printf("%lld
",ans);
144     return 0;
145 }

View Code

K：贪心+单调栈

把问题想象成把一个个元素放到后面填上去

如果当前元素$a[i]$小于答案序列的最后一个元素$b[j]$，这个位置放$a[i]$会更优秀，但必须保证序列合法。

那么如果$b[j]$可以被删除，仅当$i$小于$b[j]$在原序列中最后一次出现的位置

如果$a[i]$大于等于$b[j]$就没有删除的必要了

可能有多个$b[j]$被同时删除，用单调栈维护答案序列即可

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define ll long long
 5 using namespace std;
 6 const int N1=1000005;
 7 
 8 template <typename _T> void read(_T &ret)
 9 {
10     ret=0; _T fh=1; char c=getchar();
11     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
12     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
13     ret=ret*fh;
14 }
15 
16 int n,K;
17 int a[N1],la[N1],used[N1];
18 int stk[N1],tp;
19 
20 int main()
21 {
22     freopen("a.in","r",stdin);
23     scanf("%d%d",&n,&K);
24     for(int i=1;i<=n;i++) read(a[i]), la[a[i]]=i;
25     for(int i=1;i<=K;i++)
26     {
27         if(!la[i]){
28             puts("Kanade"); return 0;
29         }
30     }
31     for(int i=1;i<=n;i++)
32     {
33         if(used[a[i]]) continue;
34         while(tp>0&&a[i]<stk[tp])
35         {
36             if(i<la[stk[tp]]) used[stk[tp]]=0, stk[tp]=0, tp--;
37             else break;
38         }
39         stk[++tp]=a[i]; used[a[i]]=1;
40     }
41     for(int i=1;i<=tp;i++) printf("%d ",stk[i]);
42     puts("");
43     return 0;
44 }

View Code

L：LCT维护树的连通性

复习板子很开心

既然是板子题，没啥可解释的

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define ll long long
 5 using namespace std;
 6 const int N1=100005;
 7 
 8 template <typename _T> void read(_T &ret)
 9 {
10     ret=0; _T fh=1; char c=getchar();
11     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
12     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
13     ret=ret*fh;
14 }
15 
16 struct LCT{
17 int fa[N1],ch[N1][2],rev[N1];
18 int idf(int x){ return ch[fa[x]][0]==x?0:1; }
19 int isroot(int x){ return (ch[fa[x]][0]==x||ch[fa[x]][1]==x)?0:1; }
20 void revers(int x){ swap(ch[x][0],ch[x][1]); rev[x]^=1; }
21 void pushdown(int x){ if(rev[x]) revers(ch[x][0]), revers(ch[x][1]), rev[x]^=1; }
22 void rot(int x)
23 {
24     int y=fa[x],ff=fa[y],px=idf(x),py=idf(y);
25     if(!isroot(y)) ch[ff][py]=x; fa[x]=ff;
26     fa[ch[x][px^1]]=y, ch[y][px]=ch[x][px^1];
27     ch[x][px^1]=y; fa[y]=x;
28     // pushup(y), pushup(x);
29 }
30 int stk[N1],tp;
31 void splay(int x)
32 {
33     int y=x; stk[++tp]=x;
34     while(!isroot(y)){ stk[++tp]=fa[y],y=fa[y]; }
35     while(tp){ pushdown(stk[tp--]); }
36     while(!isroot(x))
37     {
38         y=fa[x];
39         if(isroot(y)) rot(x);
40         else if(idf(y)==idf(x)) rot(y),rot(x);
41         else rot(x),rot(x);
42     }
43 }
44 void access(int x){ for(int y=0;x;y=x,x=fa[x]) splay(x),ch[x][1]=y; } // pushup(x);
45 void mkroot(int x){ access(x),splay(x),revers(x); }
46 void split(int x,int y){ mkroot(x),access(y),splay(y); }
47 int fdroot(int x){ access(x),splay(x); while(ch[x][0]) pushdown(ch[x][0]),x=ch[x][0]; return x; }
48 void cut(int x,int y){ split(x,y); fa[x]=ch[y][0]=0; } //pushup(y);
49 void link(int x,int y){ split(x,y); fa[x]=y; } 
50 int isconn(int x,int y){ mkroot(x); return fdroot(y)==x?1:0; } 
51 }s;
52 
53 int n,m,de;
54 
55 int main()
56 {
57     freopen("a.in","r",stdin);
58     read(n), read(m);
59     int x,y,ans; char str[10];
60     for(int i=1;i<=m;i++)
61     {
62         scanf("%s",str); read(x), read(y);
63         if(str[0]=='+') s.link(x,y);
64         if(str[0]=='-') s.cut(x,y);
65         if(str[0]=='?') 
66         {
67             ans=s.isconn(x,y);
68             if(ans) puts("Yes");
69             else puts("No");
70         }
71     }
72     return 0;
73 }

View Code

M：待填坑（在学KD树）

N：树链剖分

又是一道板子题，把树剖复习了

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define ll long long
  5 using namespace std;
  6 const int N1=100005;
  7 const int p=170001;
  8 
  9 template <typename _T> void read(_T &ret)
 10 {
 11     ret=0; _T fh=1; char c=getchar();
 12     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
 13     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
 14     ret=ret*fh;
 15 }
 16 struct Edge{
 17 int to[N1*2],nxt[N1*2],head[N1],cte;
 18 void ae(int u,int v)
 19 { cte++; to[cte]=v, nxt[cte]=head[u], head[u]=cte; }
 20 }e;
 21 struct SEG{
 22 int sum[N1<<2],tag[N1<<2]; //****二倍
 23 void pushdown(int l,int r,int rt)
 24 {
 25     if(!tag[rt]) return;
 26     int mid=(l+r)>>1;
 27     (sum[rt<<1]+=1ll*tag[rt]*(mid-l+1)%p)%=p;
 28     (sum[rt<<1|1]+=1ll*tag[rt]*(r-mid)%p)%=p;
 29     (tag[rt<<1]+=tag[rt])%=p;  //***标记也要更新
 30     (tag[rt<<1|1]+=tag[rt])%=p;
 31     tag[rt]=0;
 32 }
 33 void pushup(int rt){ sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%p; }
 34 void upd(int L,int R,int l,int r,int rt,int w)
 35 {
 36     if(L<=l&&r<=R)
 37     { 
 38         (sum[rt]+=1ll*w*(r-l+1)%p)%=p; 
 39         (tag[rt]+=w)%=p; 
 40         return; 
 41     }
 42     int mid=(l+r)>>1; pushdown(l,r,rt);
 43     if(L<=mid) upd(L,R,l,mid,rt<<1,w);
 44     if(R>mid) upd(L,R,mid+1,r,rt<<1|1,w);
 45     pushup(rt);
 46 }
 47 int query(int L,int R,int l,int r,int rt)
 48 {
 49     if(L<=l&&r<=R){ return sum[rt]; }
 50     int mid=(l+r)>>1,ans=0; pushdown(l,r,rt);
 51     if(L<=mid) (ans+=query(L,R,l,mid,rt<<1))%=p;
 52     if(R>mid) (ans+=query(L,R,mid+1,r,rt<<1|1))%=p;
 53     return ans;
 54 }
 55 }s;
 56 
 57 int n,m,de;
 58 int pos[N1],sz[N1],son[N1],fa[N1],dep[N1],tp[N1],tot;
 59 void dfs1(int u,int dad)
 60 {
 61     sz[u]=1;
 62     for(int j=e.head[u];j;j=e.nxt[j])
 63     {
 64         int v=e.to[j]; if(v==dad) continue;
 65         fa[v]=u, dep[v]=dep[u]+1;
 66         dfs1(v,u); sz[u]+=sz[v];
 67         son[u]=sz[v]>sz[son[u]]?v:son[u];
 68     }
 69 }
 70 void dfs2(int u)
 71 {
 72     pos[u]=++tot;
 73     if(son[u]) tp[son[u]]=tp[u], dfs2(son[u]);
 74     for(int j=e.head[u];j;j=e.nxt[j])
 75     {
 76         int v=e.to[j];
 77         if(v==fa[u]||v==son[u]) continue;
 78         tp[v]=v; dfs2(v);
 79     }
 80 }
 81 void update(int x,int y,int w)
 82 {
 83     while(tp[x]!=tp[y])
 84     {
 85         if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
 86         s.upd(pos[tp[x]],pos[x],1,n,1,w);
 87         x=fa[tp[x]];
 88     }
 89     if(dep[x]>dep[y]) swap(x,y);
 90     s.upd(pos[x],pos[y],1,n,1,w);
 91 }
 92 int query(int x,int y)
 93 {
 94     int ans=0;
 95     while(tp[x]!=tp[y])
 96     {
 97         if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
 98         (ans+=s.query(pos[tp[x]],pos[x],1,n,1))%=p;
 99         x=fa[tp[x]];
100     }
101     if(dep[x]>dep[y]) swap(x,y);
102     (ans+=s.query(pos[x],pos[y],1,n,1))%=p;
103     return ans;
104 }
105 int a[N1];
106 
107 int main()
108 {
109     freopen("a.in","r",stdin);
110     read(n); read(m); int q,x,y,z,ans;
111     for(int i=1;i<=n;i++) read(a[i]);
112     for(int i=1;i<n;i++) read(x), read(y), e.ae(x,y), e.ae(y,x);
113     dep[1]=1; dfs1(1,-1);
114     tp[1]=1; dfs2(1);
115     for(int i=1;i<=n;i++) s.upd(pos[i],pos[i],1,n,1,a[i]);
116     for(int i=1;i<=m;i++)
117     {
118         read(q);
119         if(q==1){
120             read(x), read(y), read(z);
121             update(x,y,z);
122         }else{
123             read(x), read(y);
124             ans=query(x,y);
125             printf("%d
",ans);
126         }
127     }
128     return 0;
129 }
130 
131 // int lca(int x,int y)
132 // {
133 //     while(tp[x]!=tp[y])
134 //     {
135 //         if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
136 //         x=fa[tp[x]];
137 //     }
138 //     return dep[x]<dep[y]?x:y;
139 // }

View Code

O：线段树上二分

又又是一道板子题

线段树维护区间最大值

询问怎么处理？询问的区间一定挂在$O(logn)$个线段树区间上，从左到右依次考虑每个线段树区间内是否存在某点符合要求，符合要求就在这个线段树区间内二分，总复杂度$O(mlogn)$

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define ll long long
 5 using namespace std;
 6 const int N1=2000005;
 7 const int inf=0x3f3f3f3f;
 8 
 9 template <typename _T> void read(_T &ret)
10 {
11     ret=0; _T fh=1; char c=getchar();
12     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
13     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
14     ret=ret*fh;
15 }
16 
17 int n,m;
18 int a[N1];
19 
20 struct SEG{
21 int ma[N1<<2];
22 void pushup(int rt){ ma[rt]=max(ma[rt<<1],ma[rt<<1|1]); }
23 void upd(int x,int l,int r,int rt,int w)
24 {
25     if(l==r){ ma[rt]=w; return; }
26     int mid=(l+r)>>1;
27     if(x<=mid) upd(x,l,mid,rt<<1,w);
28     else upd(x,mid+1,r,rt<<1|1,w);
29     pushup(rt);
30 }
31 int found,ans;
32 void find(int l,int r,int rt,int w)
33 {
34     if(l==r){ ans=l; return; }
35     int mid=(l+r)>>1; 
36     if(ma[rt<<1]>=w) find(l,mid,rt<<1,w);
37     else find(mid+1,r,rt<<1|1,w);
38 }
39 void qlst(int L,int R,int l,int r,int rt,int w)
40 {
41     if(L<=l&&r<=R){ 
42         if(ma[rt]>=w&&!found) find(l,r,rt,w), found=1;
43         return ; 
44     }
45     int mid=(l+r)>>1; 
46     if(L<=mid&&!found) qlst(L,R,l,mid,rt<<1,w);
47     if(R>mid&&!found) qlst(L,R,mid+1,r,rt<<1|1,w);
48 }
49 int query(int L,int R,int w)
50 {
51     found=0, ans=-1;
52     qlst(L,R,1,n,1,w);
53     return ans;
54 }
55 }s;
56 
57 int main()
58 {
59     read(n); int x,y,ans;
60     for(int i=1;i<=n;i++) read(a[i]), s.upd(i,1,n,1,a[i]);
61     read(m); 
62     for(int i=1;i<=m;i++)
63     {
64         read(x), read(y); x++, y=y-i+1;
65         ans=s.query(x,n,y);
66         if(ans==-1&&x>1) ans=s.query(1,x-1,y);
67         if(ans==-1){ puts("-1"); continue; }
68         if(ans>=x) printf("%d
",ans-x);
69         else printf("%d
",n-(x-ans));
70         s.upd(ans,1,n,1,-inf);
71     }
72     return 0;
73 }

View Code

P：线段树+打表

好题，赞

一开始觉得线段树做不了写了个分块做法，卡了好久的常还是T。。看了眼题解，原来线段树可以做啊qwq

首先推一下公式，我们有$x^{varphi (n)}=1(modspace p)$

那么$x^{yspace modspacevarphi (p)}=1(modspace p)$，且$varphi (p)=p-1$

现在只考虑指数$5^{k}space modspace (p-1)$，然后怎么办？似乎并没有什么可做的手段了啊

打表发现$5^{k}space modspace (p-1)$的值竟然以27为循环节！

那么问题转化成，现在有一个序列，每个位置有27种取值，取值构成一个环。每次修改让一段区间内的所有位置都取下一个值

考虑用线段树维护，每个线段树区间根据其子区间的信息也可以得到27种取值

还需要记录$pos$，表示当前线段树区间取的是第几个位置的值，再用标记$tag$维护$pos$数组

  1 #include <ctime>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #pragma GCC optimize(3)
  6 #define ll long long
  7 using namespace std;
  8 const int N1=200005;
  9 const int ma=27;
 10 const int p=73156157;
 11 const int phip=73156156;
 12 
 13 template <typename _T> void read(_T &ret)
 14 {
 15     ret=0; _T fh=1; char c=getchar();
 16     while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
 17     while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }
 18     ret=ret*fh;
 19 }
 20 ll qpow(ll x,ll y)
 21 {
 22     ll ans=1;
 23     for(;y;x=x*x%p,y>>=1) if(y&1) ans=ans*x%p;
 24     return ans;
 25 }
 26 inline ll pow5(int x){ return 1ll*x*x%p*x%p*x%p*x%p; }
 27 
 28 int n,m,de;
 29 int a[N1];
 30 
 31 struct SEG{
 32 int sum[N1<<2][27],tag[N1<<2],pos[N1<<2];
 33 void pushdown(int rt)
 34 {
 35     if(!tag[rt]) return;
 36     (pos[rt<<1]+=tag[rt])%=ma, (pos[rt<<1|1]+=tag[rt])%=ma;
 37     (tag[rt<<1]+=tag[rt])%=ma, (tag[rt<<1|1]+=tag[rt])%=ma;
 38     pos[rt]=tag[rt]=0;
 39 }
 40 void pushup(int rt)
 41 {
 42     for(int j=0;j<ma;j++) 
 43         sum[rt][j]=(sum[rt<<1][(j+pos[rt<<1])%ma]+sum[rt<<1|1][(j+pos[rt<<1|1])%ma])%p;
 44 }
 45 void add(int L,int R,int l,int r,int rt)
 46 {
 47     if(L<=l&&r<=R){ (pos[rt]+=1)%=ma; (tag[rt]+=1)%=ma; return; }
 48     int mid=(l+r)>>1; pushdown(rt);
 49     if(L<=mid) add(L,R,l,mid,rt<<1);
 50     if(R>mid) add(L,R,mid+1,r,rt<<1|1);
 51     pushup(rt);
 52 }
 53 int query(int L,int R,int l,int r,int rt)
 54 {
 55     if(L<=l&&r<=R){ return sum[rt][pos[rt]]; }
 56     int mid=(l+r)>>1,ans=0; pushdown(rt);
 57     if(L<=mid) (ans+=query(L,R,l,mid,rt<<1))%=p;
 58     if(R>mid) (ans+=query(L,R,mid+1,r,rt<<1|1))%=p;
 59     pushup(rt);
 60     return ans;
 61 }
 62 void build(int l,int r,int rt)
 63 {
 64     if(l==r){
 65         sum[rt][0]=a[l];
 66         for(int j=1;j<ma;j++) sum[rt][j]=pow5(sum[rt][j-1]);
 67         return;
 68     }
 69     int mid=(l+r)>>1;
 70     build(l,mid,rt<<1);
 71     build(mid+1,r,rt<<1|1);
 72     pushup(rt);
 73 }
 74 }s;
 75 
 76 int main()
 77 {
 78     freopen("a.in","r",stdin);
 79     // freopen("a.out","w",stdout);
 80     // clock_t sta,ed;
 81     // sta=clock();
 82     read(n); read(m); 
 83     int fl,x,y; ll ans;
 84     for(int i=1;i<=n;i++) read(a[i]);
 85     s.build(1,n,1);
 86     for(int j=1;j<=m;j++)
 87     {
 88         read(fl), read(x), read(y);
 89         if(fl==1){
 90             s.add(x,y,1,n,1);
 91         }else{
 92             ans=0;
 93             ans=s.query(x,y,1,n,1);
 94             ans=ans*qpow(y-x+1,p-2)%p;
 95             printf("%lld
",ans);
 96         }
 97     }
 98     // ed=clock(); printf("%.7lf s
",(double)(ed-sta)/CLOCKS_PER_SEC);
 99     // printf("%.7lf s
",(double)(tot)/CLOCKS_PER_SEC);
100     return 0;
101 }

View Code