A-做游戏

题目描述

牛牛和 牛可乐在玩石头剪刀布。
众所周知，石头剪刀布的规则是这样的：
在一局游戏中，双方各自出石头、剪刀、布其一。
胜负关系如下：

牛牛和牛可乐进行了多轮游戏，牛牛总共出了A次石头，B次剪刀，C次布；牛可乐总共出了 X次石头，Y次剪刀，Z次布。你需要求出牛牛最多获胜多少局。

输入描述

第一行，三个非负整数 A,B,C 。
第二行，三个非负整数 X,Y,Z 。
保证$ A+B+C=X+Y+Z, 0≤A,B,C,X,Y,Z≤1000000000$。

输出描述

输出一行，一个整数表示答案。

示例1

输入
114514 0 0
0 114514 0
输出
114514

思路

尽可能让牛牛的每次出 剪刀/石头/布 对应到牛可乐出 布/剪刀/石头。
ans=min(A,Y)+min(B,Z)+min(C,X)ans=min(A,Y)+min(B,Z)+min(C,X)。
时间复杂度 O(1)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
      	long long  a,b,c;
      	long long x,y,z;
      	scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&x,&y,&z);
      	long long ans=0;
      	ans+=min(a,y);
      	ans+=min(b,z);
      	ans+=min(c,x);
     	printf("%lld",ans);
     	return 0;
}

B-排数字

题目描述

牛可乐最喜爱的字符串是616。
牛可乐得到了一个纯数字的字符串S，他想知道在可以任意打乱顺序的情况下，最多有多少个不同的子串为616。
当两个子串S1[l1...r1],S2=[l2...r2]S_1[l_1...r_1],S_2=[l_2...r_2]满足l1≠l2l_1≠l_2或r1≠r2r_1≠r_2时，它们被认为是不同的。

输入描述

第一行，一个正整数 |S|，表示 S 的长度。
第二行，一个字符串 S，其字符集为 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。
保证 1≤∣S∣≤200000

输入描述

输出一行，一个整数表示答案。

示例1

输入
11
11451419266
输出
1
说明
一种最优打乱方案为 “11451492616”，有一个子串为 “616” 。

思路

因为字符串可以任意打乱，1和6以外不需要考虑。
要让 616子串最多一定是61616… ，这样后面的串可以用前面的6。
数量为min(cnt6−1,cnt1)min(cnt_6-1,cnt_1)（可以理解为前面一个6后面1616… 循环）
时间复杂度 O(|S|) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<algorithm>
using namespace std;
char s[200007];
int main()
{
       int n;
       scanf("%d\n%s",&n,s+1);
       int i;
       int c6=0,c1=0;
       for(i=1;i<=n;i++)
       {
           if(s[i]=='6') c6++;
           else if(s[i]=='1')c1++; 
       }
       int ans;
       ans=min(c6-1,c1);
       printf("%d",ans);
       return 0;
}

C-算概率

题目描述

牛牛刚刚考完了期末，尽管牛牛做答了所n 道题目，但他不知道有多少题是正确的。
不过，牛牛知道第i道题的正确率是pip_i，牛牛想知道这n题里恰好有 0,1,…,n 题正确的概率分别是多少，对1000000007取模。
对1000000007 取模的含义是：对于一个b≠0的不可约分数 a/ba/b，存在q 使得 b×qb×q modmod (1000000007)=a(1000000007) =a，q 即为 a/b 对1000000007取模的结果。

输入描述

第一行，一个正整数nn。
第二行，nn个整数 p1,p2,…,pnp_1,p_2,…,p_n，在模1000000007意义下给出。
保证 1≤n≤20001≤n≤2000。

输出描述

输出一行n+1n+1个用空格隔开的整数表示答案（对1000000007取模）。

示例1

输入
1
500000004
输出
500000004 500000004
说明
有 1 道题，做对的概率是1/2在模1000000007意义下为 500000004 ）。

思路

一道可以dp的题目，dp[i][j]表示前i题做对j题的概率，最后一次输出dp[n][j]即可。转移方程讨论的就是第j题是否做对。
需要注意的是取模意义下的概率运算。
做对的概率是p[i],那么做错的概率就是(mod+1-p[i])。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#define N 2333
using namespace std;
const int mod=1e9+7;
long long dp[N][N],p[N];
int main()
{
       ios::sync_with_stdio(false);
       int n;
       cin>>n;
       int i;
       for(i=1;i<=n;i++) cin>>p[i];
       int j;
       //dp[i][j]表示前i题做对了j题 
       dp[0][0]=1;//前0题做对0题的概率必是1
       for(i=1;i<=n;i++)
       {
           dp[i][0]=dp[i-1][0]*(mod+1-p[i])%mod;
           for(j=1;j<=n;j++)
           {
               dp[i][j]=(dp[i-1][j-1]*p[i]%mod+dp[i-1][j]*(mod+1-p[i])%mod)%mod;
           }
       }
       for(j=0;j<=n;j++)
       {
           cout<<dp[n][j];
           if(j<n) cout<<' ';
       }
       return 0;
}

D-数三角

题目描述

牛牛得到了一个平面，这个平面上有 n 个不重合的点，第i个点的坐标为 (xi,yi)。
牛牛想知道，这n个点形成的三角形中，总共有多少个钝角三角形。

输入描述

第一行，一个正整数 n，表示点数。
第二行至第 n+1 行中，第 i+1 行包含两个整数xi,yi,表示第i个点的坐标。
保证1≤n≤500，−10000≤xi,yi≤100001≤n≤500，−10000≤x_i,y_i≤10000，任意两点不重合。

输出描述

输出一行，一个整数表示答案。

示例1

输入
3
0 0
-1145 1
1 0
输出
1

思路

这题的n给的数据范围较小，允许O(n³)的时间复杂度。直接暴力枚举，成钝角的必要条件是向量点积为负，需要用斜率不相等排除三点共线的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#define N 505
using namespace std;
int x[N],y[N];
bool check(int i,int j,int k)
{
       return (x[i]-x[k])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[k])<0/*向量表示钝角*/&&(y[i]-y[j])*(x[j]-x[k])!=(y[j]-y[k])*(x[i]-x[j])/*这是斜率不相等化简的结果*/;
}
int main()
{
       ios::sync_with_stdio(false);
       int n;
       cin>>n;
       int i,j,k;
       for(i=1;i<=n;i++)
       {
           cin>>x[i]>>y[i];
       }
       int ans=0;
       for(i=1;i<=n;i++)
       {
           for(j=i+1;j<=n;j++)
           {
               for(k=j+1;k<=n;k++)
     	       {
                   if(check(i,j,k)||check(k,i,j)||check(j,i,k))
                   ans++;
               }
           }
       }
       cout<<ans;
       return 0;
}

E-做计数

题目描述

这一天，牛牛与 牛魔王相遇了――然而这并不在牛牛期望之中。
牛魔王不出意料又给牛牛一道看似很难的题目：
求有多少个不同的正整数三元组 (i,j,k)(i,j,k)满足i+j=k\sqrt i+\sqrt j=\sqrt k。
当两个三元组(i1,j1,k1)(i_1,j_1,k_1),$ (i_2,j_2,k_2)满足满足i_1≠i_2或或j_1≠j_2或或k_1≠k_2$时，它们被认为是不同的。

输入描述

第一行，一个整数nn。
保证 1≤n≤400000001≤n≤40000000。

输出描述

输出一行，一个整数表示答案。

思路

i,ji,j为完全平方数，所以 i⋅ji·j 为完全平方数。
令v=ijv=\sqrt {ij},则v2≤nv^2≤n。枚举vv，然后找到v2v^2的因子个数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int main()
{
       ios::sync_with_stdio(false);
       int n;
       cin>>n;
       int i,v;
       int ans=0;
       for(v=1;v*v<=n;v++)
       {
           for(i=1;i<v;i++)
           {
               if(!(v*v%i)) ans+=2;
           }
           ans++;//加上v==i重复的情况
       }
       cout<<ans;
       return 0;
}

F-拿物品

题目描述

牛牛和牛可乐面前有nn个物品，这些物品编号为1,2,…,n1,2,…,n，每个物品有两个属性ai,bia_i,b_i。
牛牛与牛可乐会轮流从剩下物品中任意拿走一个，牛牛先选取。
设牛牛选取的物品编号集合为 H,牛可乐选取的物品编号的集合为TT，取完之后，牛牛得分为∑ai(i∈H)∑a_i(i∈H),牛可乐得分为∑bi(i∈T)∑b_i(i∈T)。
牛牛和牛可乐都希望最大化自己与对方得分的差。
你需要求出两人都使用最优策略的情况下，最终分别会选择哪些物品，若有多种答案或输出顺序，输出任意一种。

输入描述

第一行，一个正整数 nn，表示物品个数。
第二行，$n $个整数 a1,a2,...,ana_1,a_2,...,a_n，表示 nn 个物品的 A 属性。
第三行，nn 个整数 b1,b2,...,bnb_1,b_2,...,b_n，表示 $n 个物品的B属性。保证个物品的 B 属性。 保证 2≤n≤2×10^5，0≤a≤10^9$。

输出描述

输出两行，分别表示在最优策略下牛牛和牛可乐各选择了哪些物品，输出物品编号。

示例1

输入
3
8 7 6
5 4 2
输出
1 3
2
说明
3 1
2
也会被判定为正确

思路

假设物品已经被选完，此时牛牛选择的物品A属性的价值和是N,牛可乐选择的物品B属性价值和是M 。
如果 牛牛的 (a1,b1)(a_1,b_1)物品与牛可乐的 (a2,b2)(a_2,b_2)换，则N′=N−a1+a2,M′=M+b1−b2N'=N-a_1+a_2, M'=M+b_1-b_2，对于牛牛（目标是最大化 N-M）来说会变得更优仅当 a1+b1<a2+b2a_1+b_1<a_2+b_2，对于牛可乐（目标也是最大化N-M）也同理。所以两人都会优先选择$ a_i+b_i最大的物品。此题重点在分差最大。牛牛每取一件物品，会得到最大的物品。 此题重点在分差最大。牛牛每取一件物品，会得到a_i的属性，并且让牛可乐失去了的属性，并且让牛可乐失去了b_i的属性，所以牛牛实际上得到了的属性，所以牛牛实际上得到了a_i+b_i$的属性，牛可乐的取法同理，因此，这题的思想就转变为贪心。
将物品按照两个属性的和从大到小排序，依次分给两人即可。
时间复杂度 O(nlogn)O(nlogn)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<algorithm>
using namespace std;
struct Goods
{
    int a,b,id;
}goods[200009];
bool cmp(Goods p,Goods q)
{
    return p.a+p.b>q.a+q.b;
}
int main()
{
       int n;
       scanf("%d",&n);
       int i;
       for(i=1;i<=n;i++)
       {
           scanf("%d",&goods[i].a);
           goods[i].id=i;
       }
       for(i=1;i<=n;i++)
       {
           scanf("%d",&goods[i].b);
       }
       sort(goods+1,goods+1+n,cmp);
       for(i=1;i<=n;i+=2)
       {
           printf("%d ",goods[i].id);
       }
       putchar('\n');
       for(i=2;i<=n;i+=2)
       {
           printf("%d ",goods[i].id);
       }
       return 0;
}

G-判正误

题目描述

牛可乐有七个整数a,b,c,d,e,f,ga,b,c,d,e,f,g并且他猜ad+be+cf=ga^d+b^e+c^f=g。但牛可乐无法进行如此庞大的计算。
请验证牛可乐的猜想是否成立。

输入描述

第一行一个正整数 T，表示有 T 组数据。
每组数据输入一行七个整数a,b,c,d,e,f,ga,b,c,d,e,f,g。
保证1≤T≤1000,−109≤a,b,c,g≤109，0≤d,e,f≤1091≤T≤1000, −10^9≤a,b,c,g≤10^9，0≤d,e,f≤10^9。保证不会出现指数和底数同为 0 的情况。

输出描述

每组数据输出一行，若猜想成立，输出 Yes，否则输出No。

示例1

输入
2
1 1 4 5 1 4 258
114514 1919810 1 2 3 4 1
输出
Yes
No
说明
1⁵+1¹+4⁴=258
114514²+1919810³+1⁴≠1

思路

直接计算会 TLE / MLE ，考虑用快速幂在模意义下进行计算，若 ad+be+cf≡g(modM)a^d+b^e+c^f ≡ g(mod M)，则原式有概率成立，多选择一些模数以提高正确率。
实际情况是，取mod=1e9+7通过样例0.00%，其他取随便取一个10位数的mod基本都能过。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
const long long mod=2368711239;
long long qpow(long long a,long long b)
{
      long long ans=1;
      a=a%mod;
      while(b)
      {
          if(b&1) ans=(ans*a)%mod;
          a=a*a%mod;
          b>>=1;
      }
      return ans;
}
int main()
{
      ios::sync_with_stdio(false);
      int t;
      cin>>t;
      while(t--)
      {
          long long a,b,c,d,e,f,g;
          cin>>a>>b>>c>>d>>e>>f>>g;
          if((qpow(a,d)+qpow(b,e)+qpow(c,f))%mod==g%mod)cout<<"Yes"<<endl;
          else cout<<"No"<<endl;
      }
      return 0;
}

H-施魔法

题目描述

牛可乐有n个元素(编号1…n)，第i个元素的能量值为$ ai。牛可乐可以选择至少k个元素来施放一次魔法，魔法消耗的魔力是这些元素能量值的极差。形式化地，若所用元素编号集合为S，则消耗的魔力为。 牛可乐可以选择至少k个元素来施放一次魔法，魔法消耗的魔力是这些元素能量值的极差。形式化地，若所用元素编号集合为S，则消耗的魔力为max{a_i}-min{a_i}(i∈S)$。
牛可乐要求每个元素必须被使用恰好一次。
牛可乐想知道他最少需要多少魔力才能用完所有元素，请你告诉他。

输入描述

第一行两个整数n,k。
第二行n个整数a1,a2,...,ana_1,a_2,...,a_n。
保证1≤k,n≤3×105，0≤ai≤1091≤k,n≤3×10^5，0≤a_i≤10^9。

输出描述

输出一行，一个整数表示答案。

示例1

输入
4 2
8 7 114514 114513
输出
2
说明
使用第1、2个元素施放一次魔法，消耗魔力为8-7=1；第3、4个元素施放一次魔法，消耗魔力为114514-114513=1；两个魔法一共消耗2点魔力。

思路1

要使每个连连续区间极差之和最小，势必要将a数组从小到大排序。
令dp[i]表示用掉前i个元素的最小代价，则有：
dp[i]=mindp[j−1]+a[i]−a[j]=mindp[j−1]−a[j]+a[i]dp[i] = min{ dp[j-1] + a[i]- a[j] }=min{ dp[j-1]-a[j] } + a[i],因为至少选择k个元素，于是有j∈[1,i-k+1]。于是只需要通过迭代的方式，滚动更新mindp[i−1]−a[i]min { dp[i-1] - a[i]},就能在O(n)O(n)的时间内更新dp数组。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<algorithm>
#define N 300008
#define init 190283746
int dp[N];//干掉前i个元素的最小值
int a[N];
using namespace std;
int main()
{
       ios::sync_with_stdio(0);
       int n,k;
       cin>>n>>k;
       int i;
       for(i=1;i<=n;i++) cin>>a[i];
       fill(dp+1,dp+1+n,init);
       sort(a+1,a+1+n);
       int pre=-a[1];
       for(i=k;i<=n;i++) 
       {
           dp[i]=pre+a[i];            
           pre=min(pre,dp[i-k+1]-a[i-k+2]);//在循环的同时非常巧妙的将j遍历了1~i-k+1
       }
       cout<<dp[n];
       return 0;
}

思路2

dp[i]就是前i个元素以i为尾划分段的最小值。
i可以是作为前一段的新尾，dp[i]=dp[i−1]−a[i−1]+a[i]dp[i]=dp[i-1]-a[i-1]+a[i]。
也可是新开一段k，作为段尾 $dp[i]=dp[i-k]-a[i-k+1]+a[i] $(a[i-k+1]是头，a[i]是尾)
则动态转移方程为 dp[i]=min(dp[i−1]−a[i−1]+a[i],dp[i−k]−a[i−k+1]+a[i])dp[i]=min(dp[i-1]-a[i-1]+a[i],dp[i-k]-a[i-k+1]+a[i])。
需要注意的是1~k必须组成一个段，所以循环从 k+1 开始。

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
#define N 300008
#define init 190283746
int dp[N];//干掉前i个元素的最小值
int a[N];
using namespace std;
int main()
{
       ios::sync_with_stdio(0);
       int n,k;
       cin>>n>>k;
       int i;
       for(i=1;i<=n;i++) cin>>a[i];
       fill(dp+1,dp+1+n,init);
       sort(a+1,a+1+n);
       dp[k]=a[k]-a[1];
       for(i=k+1;i<=n;i++) dp[i]=min(dp[i-1]-a[i-1],dp[i-k]-a[i-k+1])+a[i];
       cout<<dp[n];
       return 0;
}

I-建通道

题目描述

在无垠的宇宙中，有 n 个星球，第 i 个星球有权值 vi。
由于星球之间距离极远，因此想在有限的时间内在星际间旅行，就必须要在星球间建立传送通道。
任意两个星球之间均可以建立传送通道，不过花费并不一样。第 i 个星球与第 j 个星球的之间建立传送通道的花费是lowbit(vi⊕vj)。
，其中⊕ 为二进制异或，而 lowbit(x)为x二进制最低位1对应的值，例如lowbit(5)=1,lowbit(8)=8。特殊地，lowbit(0)=0。
牛牛想在这n个星球间穿梭，于是――你需要告诉牛牛，要使这n个星球相互可达，需要的花费最少是多少。

输入描述

第一行，一个整数nn。
第二行，nn个非负整数v1,v2,v3,...,vnv_1,v_2,v_3,...,v_n。
保证1≤n≤200000,0≤vi≤2301≤n≤200000, 0≤vi≤2^{30}。

输出描述

输出一行，一个整数表示答案。

思路

首先将权值去重（权值相等的点连接代价为 0），设去重后有num个点，接下来找到最小的二进制位k，满足存在vi的这个二进制位是0，且存在vjv_j的这个二进制位是1 ，答案就是 2k×(m−1)2^k×(m-1)（相当于所有这位是0的点与j点连边，是1的点与i点连边）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int v[200003];
int n;
int main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	int i;
	for(i=1;i<=n;i++) cin>>v[i];
	//去重 
	sort(v+1,v+1+n);
	int num=unique(v+1,v+1+n)-(v+1);
	int va=v[1],vo=v[1];
	for(i=2;i<=num;i++)
	{
		va&=v[i];
		vo|=v[i];
	}
	va^=vo;
	ll ans=0;
	for(i=0;i<=30;i++)
	{
		if((va>>i)&1)
		{
			ans=(ll)(num-1)*(ll)(1<<i);
			break;
		}
	}
	cout<<ans;
	return 0;
}

J-求函数

题目描述

牛可乐有$ n$ 个一次函数，第ii个函数为$ f_i(x)=k_i·x+b_i。牛可乐有m次操作，每次操作为以下二者其一：⋅1ikb,将。 牛可乐有m次操作，每次操作为以下二者其一： ·1 i k b ,将f_i(x)修改为修改为f_i(x)=kx+b。⋅2lr，求。 ·2 l r，求f_r(f_{r-1} (…(f_ {l+1}(f_l(1)))…))$。
牛可乐当然(bu)会做啦，他想考考你——
答案对1000000007取模。

输入描述

第一行，两个整数n,mn,m。
第二行，nn个整数k1,k2...,knk_1,k_2...,k_n。
第三行，n个整数b1,b2,...bnb_1,b_2,...b_n。
接下来m行，每行一个操作，格式见上。
保证1≤n,m≤200000，0≤ki,bi≤10000000071≤n,m≤200000，0≤k_i,b_i≤1000000007。

输出描述

对于每个求值操作，输出一行一个整数，表示答案。

示例1

输入
2 3
1 1
1 0
1 2 114514 1919810
2 1 2
2 1 1
输出
2148838
2
说明
初始 f1(x)=x+1,f2(x)=xf_1(x)=x+1,f_2(x)=x
修改后 f2(x)=114514x+1919810f_2(x)=114514x+1919810
查询时 f1(1)=2,f2(f1(1))=2148838f_1(1)=2, f2(f_1(1))=2148838

思路

又是更改，又是查询，当然是要用线段树啦。可以在O(nlogn)O(nlogn)内完成所有查询和更新的操作。
本题为单点更新、区间查询的最基础的线段树应用，难点在于函数式的化简，化简后能找到较为清晰的递推关系。

我们考虑如何PushUp,即合并区间[l1,r1],[r1+1,r2][l1,r1],[r1+1,r2]。

易得区间[l1,r2][l1,r2]的∏ki=n1×n2,∑bi∏kj=m1×n2+m2∏k_i=n_1×n_2 ,∑b_i∏k_j=m_1×n_2+m_2。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<algorithm>
#include<cstdio>
#include<iostream>
#define N 200001
#define ll long long
using namespace std;
const int mod=1e9+7;
struct node
{
	int l,r;
	ll k,b;
}tree[N<<2];
ll k[N],b[N];
int n,m;
ll ansk,ansb;
void PushUp(int id)
{
	tree[id].k=tree[id<<1].k*tree[id<<1|1].k%mod;
	tree[id].b=(tree[id<<1].b*tree[id<<1|1].k+tree[id<<1|1].b)%mod;
	return;
}
void build(int id,int l,int r)
{
	tree[id].l=l;
	tree[id].r=r;
	if(l==r)
	{
		tree[id].b=b[l];
		tree[id].k=k[l];
		return;
	}
	int mid=l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	PushUp(id);
	return;
}
void update(int id,int pos,ll kk,ll bb)
{
	if(tree[id].l==tree[id].r)
	{
		tree[id].k=kk;
		tree[id].b=bb;
		return;
	}
	int mid=tree[id].l+tree[id].r>>1;
	if(pos<=mid) update(id<<1,pos,kk,bb);
	else update(id<<1|1,pos,kk,bb);
	PushUp(id);
    return;
}
void query(int id,int l,int r)
{
	if(l<=tree[id].l&&tree[id].r<=r)
	{
		ansk=ansk*tree[id].k%mod;
		ansb=(ansb*tree[id].k+tree[id].b)%mod;
		return;
	}
	int mid=tree[id].l+tree[id].r>>1;
	if(l<=mid) query(id<<1,l,r);
	if(r>=mid+1) query(id<<1|1,l,r);
	return;
}
int main()
{
	scanf("%d%d",&n,&m);
	int i;
	for(i=1;i<=n;i++) scanf("%lld",&k[i]);	
	for(i=1;i<=n;i++) scanf("%lld",&b[i]);
	build(1,1,n);
	while(m--)
	{
		short opt;
		cin>>opt;
		if(opt==1)
		{
			int pos;
			ll kk,bb;
			scanf("%d%lld%lld",&pos,&kk,&bb);
			update(1,pos,kk,bb);
		}
		else if(opt==2)
		{
			int l,r;
			ansb=0,ansk=1;
			scanf("%d%d",&l,&r);
			query(1,l,r);
			printf("%lld\n",(ansk+ansb)%mod);
		}
	}
	return 0;
}