1 主席树区间修改
2 #define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
3 #define bug(x) cout<<#x<<" is "<<x<<endl
4 #include <bits/stdc++.h>
5 #define iter ::iterator
6 using namespace std;
7 typedef long long ll;
8 typedef pair<int,int>P;
9 #define pb push_back
10 #define mk make_pair
11 #define se second
12 #define fi first
13 const ll mod=1e9+7;
14 const int N=1e5+5;
15 int n,q;
16 int a[N],rt[N*25],ls[N*25],rs[N*25];
17 ll sum[N*25],add[N*25];
18 int cnt;
19 void build(int &o,int l,int r){
20 o=++cnt;
21 if(l==r){
22 sum[o]=a[l];
23 return;
24 }
25 int m=(l+r)/2;
26 build(ls[o],l,m);
27 build(rs[o],m+1,r);
28 sum[o]=sum[ls[o]]+sum[rs[o]];
29 }
30 void up(int &o,int pre,int l,int r,int ql,int qr,int val){
31 o=++cnt;
32 ls[o]=ls[pre];
33 rs[o]=rs[pre];
34 add[o]=add[pre];
35 sum[o]=sum[pre]+1ll*val*(min(r,qr)-max(l,ql)+1);
36 if(l>=ql&&r<=qr){
37 add[o]+=val;
38 return;
39 }
40 int m=(l+r)/2;
41 if(ql<=m)up(ls[o],ls[pre],l,m,ql,qr,val);
42 if(qr>m)up(rs[o],rs[pre],m+1,r,ql,qr,val);
43 }
44 ll qu(int o,int l,int r,int ql,int qr){
45 if(l>=ql&&r<=qr)return sum[o];
46 ll res=add[o]*(min(r,qr)-max(l,ql)+1);
47 int m=(l+r)/2;
48 if(ql<=m)res+=qu(ls[o],l,m,ql,qr);
49 if(qr>m)res+=qu(rs[o],m+1,r,ql,qr);
50 return res;
51 }
52 int main(){
53 while(~scanf("%d%d",&n,&q)){
54 for(int i=1;i<=n;i++)scanf("%d",&a[i]);
55 cnt=0;
56 build(rt[0],1,n);
57 int time=0;
58 while(q--){
59 char op;
60 int L,R,val;
61 scanf(" %c",&op);
62 if(op=='Q'){
63 scanf("%d%d",&L,&R);
64 ll ans=qu(rt[time],1,n,L,R);
65 printf("%lld\n",ans);
66 }
67 else if(op=='C'){
68 scanf("%d%d%d",&L,&R,&val);
69 ++time;
70 up(rt[time],rt[time-1],1,n,L,R,val);
71
72 }
73 else if(op=='H'){
74 scanf("%d%d%d",&L,&R,&val);
75 ll ans=qu(rt[val],1,n,L,R);
76 printf("%lld\n",ans);
77 }
78 else{
79 scanf("%d",&val);
80 time=val;
81 }
82 }
83 printf("\n");
84 }
85 }
86
87 JAVA大数
88 import java.math.RoundingMode;
89 import java.math.BigDecimal;
90 import java.math.BigInteger;
91 import java.util.Scanner;
92 import java.util.*;
93 import java.io.*;
94 public class Main {
95 public static long mod=(long)(1e9+7);//1e9会被java看作double
96 public static long fastpow(long x, long y) {//快速幂
97 long res=1;
98 while(y>0) {
99 if((y&1)==1) {
100 res=(res*x)%mod;
101 }
102 x=(x*x)%mod;
103 y>>=1;
104 }
105 return res;
106 }
107 public static int N=200005;
108 public static long[] b=new long[N];//声明数组
109 public static void init(int n){//求n的阶乘
110 b[0]=1;
111 for(int i=1;i<=n;i++){
112 b[i]=(b[i-1]*i)%mod;
113 }
114 }
115 public static void main(String [] args){
116 Scanner cin = new Scanner(System.in);
117 int T = cin.nextInt();
118 while (T-- > 0) {
119 BigInteger x = cin.nextBigInteger();//输入大数
120 BigInteger y = cin.nextBigInteger();
121 BigInteger z = BigInteger.valueOf(123456789L);//L标记是long类型
122 BigInteger k = BigInteger.ZERO;//赋值k为大数类型的0
123 System.out.println(k);
124 System.out.println(fastpow(2L,x.longValue()));//快速幂输出2的x次方
125
126 if(x.compareTo(y)==0)System.out.println("x=y");//大数的比较函数
127 else if(x.compareTo(y)<0)System.out.println("x<y");
128 else if(x.compareTo(y)>0)System.out.println("x>y");
129 String s=x.toString(2);//把十进制大数转化为二进制数存入字符串。
130 int n=s.length();//获取字符串长度
131 for (int i = 0; i < n; i++) {
132 System.out.print(s.charAt(i) + " ");//空格隔开输出字符.
133 }
134 System.out.println();
135
136 BigInteger sum = x.add(y);
137 BigInteger difference = x.subtract(y);
138 BigInteger product = x.multiply(y);
139 BigInteger quotient = x.divide(y); // 假设y不为0
140 BigInteger remainder = x.remainder(y); // 假设y不为0
141
142 BigInteger gcd = x.gcd(y); // 最大公约数
143 BigInteger modInverse = (y.signum() > 0 && x.gcd(y).equals(BigInteger.ONE)) ? x.modInverse(y) : null; //求逆元
144 BigInteger power = x.pow(2); // x的2次幂
145 BigInteger shiftedLeft = x.shiftLeft(1); // x左移1位
146 BigInteger shiftedRight = x.shiftRight(1); // x右移1位
147 BigInteger andResult = x.and(y); // 位与
148 BigInteger orResult = x.or(y); // 位或
149 BigInteger xorResult = x.xor(y); // 位异或
150
151 System.out.println("x + y = " + sum);
152 System.out.println("x - y = " + difference);
153 System.out.println("x * y = " + product);
154 System.out.println("x / y = " + quotient);
155 System.out.println("x % y = " + remainder);
156 System.out.println("gcd(x, y) = " + gcd);
157 System.out.println("x modInverse y = " + (modInverse != null ? modInverse : "undefined (no inverse)"));
158 System.out.println("x^2 = " + power);
159 System.out.println("x << 1 = " + shiftedLeft);
160 System.out.println("x >> 1 = " + shiftedRight);
161 System.out.println("x & y = " + andResult);
162 System.out.println("x | y = " + orResult);
163 System.out.println("x ^ y = " + xorResult);
164
165 BigDecimal x1 = new BigDecimal(cin.next()); // 读取高精度小数
166 BigDecimal y1 = new BigDecimal(cin.next());
167
168 BigDecimal sum1 = x1.add(y1);
169 BigDecimal difference1 = x1.subtract(y1);
170 BigDecimal product1 = x1.multiply(y1);
171 BigDecimal quotient1 = x1.divide(y1, 10, RoundingMode.HALF_UP); // 设置结果精度为10位小数并使用四舍五入
172
173 System.out.println("x + y = " + sum1);
174 System.out.println("x - y = " + difference1);
175 System.out.println("x * y = " + product1);
176 System.out.println("x / y = " + quotient1); // 假设y不为0
177
178 BigDecimal original = new BigDecimal("123.456789");
179 BigDecimal result1 = original.setScale(3, RoundingMode.HALF_UP);// 小数点后保留3位，采用四舍五入
180 System.out.println(result1); // 输出：123.457
181 BigDecimal dividend1 = new BigDecimal("10");
182 BigDecimal divisor1 = new BigDecimal("3");
183 // 指定精度为10位小数，使用四舍五入模式
184 result1 = dividend1.divide(divisor1, 10, RoundingMode.HALF_UP);
185 System.out.println(result1); // 输出: 3.3333333333
186 }
187 cin.close();
188 }
189 }
190 /*
191 c=a.max(b); // 取a，b中较大的，a.min(b)就是取较小的
192 d=a.compareTo(b); //比较a与b的大小 d=-1小于d=0等于 d=1大于 d为int型
193 a.equals(b); // 判断a与b是否相等 相等返回true 不相等返回false
194 d=a.intValue(); // 将大数a转换为 int 类型赋值给 d
195 e=a.longValue(); // 将大数a转换为 long 类型赋值给 e
196 f=a.floatValue(); // 将大数a转换为 float 类型赋值给 f
197 g=a.doubleValue(); // 将大数a转换为 double 类型赋值给 g
198 s=a.toString(); // 将大数a转换为 String 类型赋值给 s
199 s=a.toPlainString(); //将大数a转换为String类型赋值给s，且不表示为科学计数法
200 a=BigInteger.valueOf(e); // 将 e 以大数形式赋值给大数 a e只能为long或int
201 a=newBigInteger(s, d); // 将s数字字符串以d进制赋值给大数a如果d=s字符数字的进制则等同于将数字字符串以大数形式赋值给大数a
202 String st = Integer.toString(num, base); //把int型num当10进制的数转成base进制数存入st中(base <= 35).
203 int num = Integer.parseInt(st, base); //把st当做base进制，转成10进制的int
204 (parseInt有两个参数,第一个为要转的字符串,第二个为说明是什么进制).
205 BigInter m = new BigInteger(st, base); // st是字符串，base是st的进制.
206 a=cin.nextBigInteger(b); //以b进制读入一个大数赋值给a
207 c=a.toString(b); // 将大数a以b进制的方式赋给字符串c
208 a=newBigInteger(c, b); //把c 当做“b进制“转为十进制大数赋值给a
209 */
210
211 计算几何
212 链接：https://ac.nowcoder.com/acm/contest/1112/J
213 来源：牛客网
214
215 Bobo 有一个三角形和一个矩形，他想求他们交的面积。
216 具体地，三角形和矩形由 8 个整数 x1,y1,x2,y2,x3,y3,x4,y4x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4x1,y1,x2,y2,x3,y3,x4,y4 描述。
217 表示三角形的顶点坐标是 (x1,y1),(x1,y2),(x2,y1)(x_1, y_1), (x_1, y_2), (x_2, y_1)(x1,y1),(x1,y2),(x2,y1)，
218 矩形的顶点坐标是 (x3,y3),(x3,y4),(x4,y4),(x4,y3)(x_3, y_3), (x_3, y_4), (x_4, y_4), (x_4, y_3)(x3,y3),(x3,y4),(x4,y4),(x4,y3)
219
220 把三角形的顶点里在矩形里面的点放进数组；
221 把矩形的顶点里在三角形里面的点放进数组；
222 把三角形三条边和矩形四条边的交点放进数组（规范相交）；
223 对这个数组去重并求凸包然后求凸包面积就是答案。
224 #include <bits/stdc++.h>
225 using namespace std;
226 #define ll long long
227 const int N=1e3+10;
228 double eps=1e-8;
229 double pi=acos(-1);
230 struct Point{
231 double x,y;
232 Point(double x=0,double y=0):x(x),y(y){};
233 };
234 typedef Point Vector;
235 Vector operator +(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
236 Vector operator -(Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}
237 Vector operator *(Vector A,double B){return Vector(A.x*B,A.y*B);}
238 Vector operator /(Vector A,double B){return Vector(A.x/B,A.y/B);}
239 int dcmp(double x){
240 if(fabs(x)<eps)return 0;
241 return x<0?-1:1;
242 }
243 bool operator<(const Point&a,const Point&b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
244 bool operator == (const Point &a,const Point &b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}
245 double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}
246 double Length(Vector A){return sqrt(Dot(A,A));}
247 double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
248 double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}
249 double Angle(Vector A) {return atan2(A.y, A.x);}
250
251 struct Circle{ //圆
252 Point c;
253 double r;
254 Circle(Point c = Point(0, 0), double r = 0):c(c),r(r){}
255 Point point(double a){
256 return Point(c.x+cos(a)*r,c.y+sin(a)*r);
257 }
258 };
259 double dis(Point A,Point B){
260 return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
261 }
262 int circle_circle(Circle C1,Circle C2,vector<Point>&sol){//返回圆与圆的交点个数
263 double d=Length(C1.c-C2.c);
264 if(dcmp(d)==0){
265 if(dcmp(C1.r-C2.r)==0)return -1;
266 return 0;
267 }
268 if(dcmp(C1.r+C2.r-d)<0)return 0;
269 if(dcmp(fabs(C1.r-C2.r)-d)>0)return 0;
270 double a=Angle(C2.c-C1.c);
271 double da=acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*d*C1.r));
272 Point p1=C1.point(a-da),p2=C1.point(a+da);
273 sol.push_back(p1);
274 if(p1==p2)return 1;
275 sol.push_back(p2);
276 return 2;
277 }
278
279 Point line_point(Point p,Vector v,Point q,Vector w){//直线交点
280 Vector u=p-q;
281 double t=Cross(w,u)/Cross(v,w);
282 return p+v*t;
283 }
284 bool onsegment(Point p,Point a1,Point a2){
285 if(p==a1||p==a2)return true;
286 return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;
287 }
288 bool segmentcross(Point a1,Point a2,Point b1,Point b2){
289 double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),
290 c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
291 return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
292 }
293 Point line_line(Point A,Point B,Point C,Vector D){//线段交点
294 if(segmentcross(A,B,C,D)){
295 return line_point(A,B-A,C,D-C);
296 }
297 return Point(123.456,0);
298 }
299 int tubao(Point *p,int n,Point *ch){
300 sort(p,p+n);
301 n=unique(p,p+n)-p;
302 int m=0;
303 for(int i=0;i<n;i++){
304 while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
305 ch[m++]=p[i];
306 }
307 int k=m;
308 for(int i=n-2;i>=0;i--){
309 while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
310 ch[m++]=p[i];
311 }
312 if(n>1)m--;
313 return m;
314 }
315 double tubaos(Point *p,int n){
316 double area=0;
317 for(int i=1;i<n-1;i++){
318 area+=Cross(p[i]-p[0],p[i+1]-p[0]);
319 }
320 return area/2;
321 }
322 int intubao(Point *ch,int n,Point p){
323 Vector A,B;
324 int flag=0;
325 for(int i=0;i<n;i++){
326 A=ch[(i+1)%n]-ch[i];
327 B=p-ch[i];
328 if(onsegment(p,ch[i],ch[(i+1)%n])){
329 flag=-1;
330 break;
331 }
332 else if(Cross(A,B)>0){
333 flag++;
334 }
335 }
336 if(flag==-1||flag==n)return 1;
337 return 0;
338 }
339 double x[N],y[N];
340 Point p[N],q[N],ch[N],ans[N];
341 int main(){
342 while(~scanf("%lf%lf",&x[1],&y[1])){
343 scanf("%lf%lf",&x[2],&y[2]);
344 scanf("%lf%lf",&x[3],&y[3]);
345 scanf("%lf%lf",&x[4],&y[4]);
346 int n=0;
347 p[n++]=Point(x[3],y[3]);
348 p[n++]=Point(x[4],y[3]);
349 p[n++]=Point(x[4],y[4]);
350 p[n++]=Point(x[3],y[4]);
351
352 int m=0;
353 q[m++]=Point(x[1],y[1]);
354 q[m++]=Point(x[1],y[2]);
355 q[m++]=Point(x[2],y[1]);
356
357 tubao(q,m,ch);
358 int cnt=0;
359 for(int i=0;i<n;i++){
360 if(intubao(ch,m,p[i])){
361 ans[cnt++]=p[i];
362 }
363 }
364 for(int i=0;i<m;i++){
365 if(intubao(p,n,q[i])){
366 ans[cnt++]=q[i];
367 }
368 }
369 p[n]=p[0];
370 q[m]=q[0];
371 for(int i=0;i<n;i++){
372 for(int j=0;j<m;j++){
373 Point A=line_line(p[i],p[i+1],q[j],q[j+1]);
374 if(dcmp(A.x-123.456)!=0)ans[cnt++]=A;
375 }
376 }
377 int n1=tubao(ans,cnt,ch);
378 if(n1<=2)printf("%.8lf\n",0.0);
379 else printf("%.8lf\n",tubaos(ch,n1));
380 }
381 }
382 字符串双哈希
383 https://codeforc.es/contest/1200/problem/E
384 题意：给定一堆字符串，依次插入答案串尾部，每次删掉答案串的后缀 与 待插入串的前缀的最大匹配串
385 思路：hash匹配后缀和前缀，不断更新hash值
386
387 #define bug(x) cout<<#x<<" is "<<x<<endl
388 #define IO std::ios::sync_with_stdio(0)
389 #include <bits/stdc++.h>
390 #define iter ::iterator
391 #define pa pair<int,int>
392 using namespace std;
393 #define ll long long
394 #define mk make_pair
395 #define pb push_back
396 #define se second
397 #define fi first
398 #define ls o<<1
399 #define rs o<<1|1
400 const int N=1e6+5;
401 int n;
402 ll mod[5]={1000000009,998244353};
403 ll base[5]={666127,777131};
404 ll p[N][2];
405 ll h[N][2];
406 void init(){
407 for(int i=0;i<2;i++)p[0][i]=1;
408 for(int i=1;i<=N-2;i++){
409 for(int j=0;j<2;j++){
410 p[i][j]=p[i-1][j]*base[j]%mod[j];
411 }
412 }
413 }
414 ll cal(int l,int r,int t){
415 return (h[r][t]-h[l-1][t]*p[(r-l+1)][t]%mod[t]+mod[t])%mod[t];
416 }
417 ll get(char c){
418 if('a'<=c&&c<='z')return c-'a';
419 if('A'<=c&&c<='Z')return c-'A'+26;
420 if('0'<=c&&c<='9')return c-'0'+52;
421 }
422 string s,t;
423 int main(){
424 IO;
425 cin>>n;
426 cin>>s;
427 int pre=1;
428 init();
429 for(int g=1;g<n;g++){
430 cin>>t;
431 int ns=s.length();
432 for(int i=pre;i<=ns;i++){
433 ll c=get(s[i-1]);
434 for(int j=0;j<2;j++){
435 h[i][j]=(h[i-1][j]*base[j]%mod[j]+c)%mod[j];
436 }
437 }
438 int nt=t.length();
439 ll H[2]={0};
440 pre=ns+1;
441 int id=0;
442 for(int i=1;i<=nt;i++){
443 int f=0;
444 ll c=get(t[i-1]);
445 for(int j=0;j<2;j++){
446 H[j]=(H[j]*base[j]%mod[j]+c)%mod[j];
447 if(cal(ns-i+1,ns,j)==H[j])f++;
448 }
449 if(f==2){
450 id=i;
451 }
452 if(i==ns)break;
453 }
454 s+=t.substr(id,nt-id);
455 }
456 cout<<s<<endl;
457 }
458 /*
459 7
460 RAtONC14epz KfIenADgDKDci OMmOOQOc yVrfGLV49fW1 xntodZLM5 2f7LXdzX xIhm
461 5
462 I want to order pizza
463 */
464
465 并查集、倍增
466 #include <cmath>
467 #include <cstdio>
468 #include <iostream>
469 using namespace std;
470 const int maxn = 100005, mod = 1000000007;
471 int n, m, fa[maxn][18], ans;
472 int find(int x, int k) {
473 return fa[x][k] == x ? x : fa[x][k] = find(fa[x][k], k);
474 }
475 void merge(int x, int y, int k) {
476 x = find(x, k), y = find(y, k);
477 if(x != y) fa[x][k] = y;
478 }
479 int main() {
480 scanf("%d %d", &n, &m);
481 const int maxk = floor(log2(n));
482 for(int i = 1; i <= n; ++i)
483 for(int k = 0; k <= maxk; ++k)
484 fa[i][k] = i;
485 for(int i = 1, l1, r1, l2, r2; i <= m; ++i) {
486 scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
487 for(int k = maxk; ~k; --k)
488 if(l1+(1<<k)-1 <= r1) merge(l1, l2, k), l1 += 1<<k, l2 += 1<<k;
489 }
490 for(int k = maxk; k; --k)
491 for(int i = 1; i+(1<<k)-1 <= n; ++i) {
492 int pos = find(i, k);
493 merge(i, pos, k-1), merge(i+(1<<k-1), pos+(1<<k-1), k-1);
494 }
495 for(int i = 1; i <= n; ++i)
496 if(fa[i][0] == i) ans = !ans ? 9 : ans * 10ll % mod;
497 printf("%d\n", ans);
498 return 0;
499 }
500
501
502 笛卡尔树
503 #define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
504 #define bug(x) cout<<#x<<" is "<<x<<endl
505 #include <bits/stdc++.h>
506 #define iter ::iterator
507 using namespace std;
508 typedef long long ll;
509 const int N=1e5+5;
510 int n;
511 ll a[N],b[N];
512 int st[N],ls[N],rs[N];
513 ll ans;
514 ll dfs(int u){
515 if(!u)return 0;
516 ll res=dfs(ls[u])+dfs(rs[u])+b[u];
517 ll res1=min(res,a[u]);
518 res1*=res1;
519 ans=max(ans,res1);
520 return res;
521 }
522 int main(){
523 IO;
524 cin>>n;
525 for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
526 int h=0;
527 for(int i=1;i<=n;i++){
528 int k=h;
529 while(k>0&&a[st[k]]>a[i])k--;
530 if(k>0)rs[st[k]]=i;
531 if(k<h) ls[i]=st[k+1];
532 st[++k]=i;
533 h=k;
534 }
535 ans=0;
536 dfs(st[1]);
537 cout<<ans<<endl;
538
539 }
540 /*
541 11
542 9 3 7 1 8 12 10 20 15 18 5
543 */
View Code
主席树区间修改
#define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define bug(x) cout<<#x<<" is "<<x<<endl
#include <bits/stdc++.h>
#define iter ::iterator
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define pb push_back
#define mk make_pair
#define se second
#define fi first
const ll mod=1e9+7;
const int N=1e5+5;
int n,q;
int a[N],rt[N*25],ls[N*25],rs[N*25];
ll sum[N*25],add[N*25];
int cnt;
void build(int &o,int l,int r){
o=++cnt;
if(l==r){
sum[o]=a[l];
return;
}
int m=(l+r)/2;
build(ls[o],l,m);
build(rs[o],m+1,r);
sum[o]=sum[ls[o]]+sum[rs[o]];
}
void up(int &o,int pre,int l,int r,int ql,int qr,int val){
o=++cnt;
ls[o]=ls[pre];
rs[o]=rs[pre];
add[o]=add[pre];
sum[o]=sum[pre]+1ll*val*(min(r,qr)-max(l,ql)+1);
if(l>=ql&&r<=qr){
add[o]+=val;
return;
}
int m=(l+r)/2;
if(ql<=m)up(ls[o],ls[pre],l,m,ql,qr,val);
if(qr>m)up(rs[o],rs[pre],m+1,r,ql,qr,val);
}
ll qu(int o,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr)return sum[o];
ll res=add[o]*(min(r,qr)-max(l,ql)+1);
int m=(l+r)/2;
if(ql<=m)res+=qu(ls[o],l,m,ql,qr);
if(qr>m)res+=qu(rs[o],m+1,r,ql,qr);
return res;
}
int main(){
while(~scanf("%d%d",&n,&q)){
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
cnt=0;
build(rt[0],1,n);
int time=0;
while(q--){
char op;
int L,R,val;
scanf(" %c",&op);
if(op=='Q'){
scanf("%d%d",&L,&R);
ll ans=qu(rt[time],1,n,L,R);
printf("%lld\n",ans);
}
else if(op=='C'){
scanf("%d%d%d",&L,&R,&val);
++time;
up(rt[time],rt[time-1],1,n,L,R,val);
}
else if(op=='H'){
scanf("%d%d%d",&L,&R,&val);
ll ans=qu(rt[val],1,n,L,R);
printf("%lld\n",ans);
}
else{
scanf("%d",&val);
time=val;
}
}
printf("\n");
}
}
JAVA大数
import java.math.RoundingMode;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;
import java.util.*;
import java.io.*;
public class Main {
public static long mod=(long)(1e9+7);//1e9会被java看作double
public static long fastpow(long x, long y) {//快速幂
long res=1;
while(y>0) {
if((y&1)==1) {
res=(res*x)%mod;
}
x=(x*x)%mod;
y>>=1;
}
return res;
}
public static int N=200005;
public static long[] b=new long[N];//声明数组
public static void init(int n){//求n的阶乘
b[0]=1;
for(int i=1;i<=n;i++){
b[i]=(b[i-1]*i)%mod;
}
}
public static void main(String [] args){
Scanner cin = new Scanner(System.in);
int T = cin.nextInt();
while (T-- > 0) {
BigInteger x = cin.nextBigInteger();//输入大数
BigInteger y = cin.nextBigInteger();
BigInteger z = BigInteger.valueOf(123456789L);//L标记是long类型
BigInteger k = BigInteger.ZERO;//赋值k为大数类型的0
System.out.println(k);
System.out.println(fastpow(2L,x.longValue()));//快速幂输出2的x次方
if(x.compareTo(y)==0)System.out.println("x=y");//大数的比较函数
else if(x.compareTo(y)<0)System.out.println("x<y");
else if(x.compareTo(y)>0)System.out.println("x>y");
String s=x.toString(2);//把十进制大数转化为二进制数存入字符串。
int n=s.length();//获取字符串长度
for (int i = 0; i < n; i++) {
System.out.print(s.charAt(i) + " ");//空格隔开输出字符.
}
System.out.println();
BigInteger sum = x.add(y);
BigInteger difference = x.subtract(y);
BigInteger product = x.multiply(y);
BigInteger quotient = x.divide(y); // 假设y不为0
BigInteger remainder = x.remainder(y); // 假设y不为0
BigInteger gcd = x.gcd(y); // 最大公约数
BigInteger modInverse = (y.signum() > 0 && x.gcd(y).equals(BigInteger.ONE)) ? x.modInverse(y) : null; //求逆元
BigInteger power = x.pow(2); // x的2次幂
BigInteger shiftedLeft = x.shiftLeft(1); // x左移1位
BigInteger shiftedRight = x.shiftRight(1); // x右移1位
BigInteger andResult = x.and(y); // 位与
BigInteger orResult = x.or(y); // 位或
BigInteger xorResult = x.xor(y); // 位异或
System.out.println("x + y = " + sum);
System.out.println("x - y = " + difference);
System.out.println("x * y = " + product);
System.out.println("x / y = " + quotient);
System.out.println("x % y = " + remainder);
System.out.println("gcd(x, y) = " + gcd);
System.out.println("x modInverse y = " + (modInverse != null ? modInverse : "undefined (no inverse)"));
System.out.println("x^2 = " + power);
System.out.println("x << 1 = " + shiftedLeft);
System.out.println("x >> 1 = " + shiftedRight);
System.out.println("x & y = " + andResult);
System.out.println("x | y = " + orResult);
System.out.println("x ^ y = " + xorResult);
BigDecimal x1 = new BigDecimal(cin.next()); // 读取高精度小数
BigDecimal y1 = new BigDecimal(cin.next());
BigDecimal sum1 = x1.add(y1);
BigDecimal difference1 = x1.subtract(y1);
BigDecimal product1 = x1.multiply(y1);
BigDecimal quotient1 = x1.divide(y1, 10, RoundingMode.HALF_UP); // 设置结果精度为10位小数并使用四舍五入
System.out.println("x + y = " + sum1);
System.out.println("x - y = " + difference1);
System.out.println("x * y = " + product1);
System.out.println("x / y = " + quotient1); // 假设y不为0
BigDecimal original = new BigDecimal("123.456789");
BigDecimal result1 = original.setScale(3, RoundingMode.HALF_UP);// 小数点后保留3位，采用四舍五入
System.out.println(result1); // 输出：123.457
BigDecimal dividend1 = new BigDecimal("10");
BigDecimal divisor1 = new BigDecimal("3");
// 指定精度为10位小数，使用四舍五入模式
result1 = dividend1.divide(divisor1, 10, RoundingMode.HALF_UP);
System.out.println(result1); // 输出: 3.3333333333
}
cin.close();
}
}
/*
c=a.max(b); // 取a，b中较大的，a.min(b)就是取较小的
d=a.compareTo(b); //比较a与b的大小 d=-1小于d=0等于 d=1大于 d为int型
a.equals(b); // 判断a与b是否相等 相等返回true 不相等返回false
d=a.intValue(); // 将大数a转换为 int 类型赋值给 d
e=a.longValue(); // 将大数a转换为 long 类型赋值给 e
f=a.floatValue(); // 将大数a转换为 float 类型赋值给 f
g=a.doubleValue(); // 将大数a转换为 double 类型赋值给 g
s=a.toString(); // 将大数a转换为 String 类型赋值给 s
s=a.toPlainString(); //将大数a转换为String类型赋值给s，且不表示为科学计数法
a=BigInteger.valueOf(e); // 将 e 以大数形式赋值给大数 a e只能为long或int
a=newBigInteger(s, d); // 将s数字字符串以d进制赋值给大数a如果d=s字符数字的进制则等同于将数字字符串以大数形式赋值给大数a
String st = Integer.toString(num, base); //把int型num当10进制的数转成base进制数存入st中(base <= 35).
int num = Integer.parseInt(st, base); //把st当做base进制，转成10进制的int
(parseInt有两个参数,第一个为要转的字符串,第二个为说明是什么进制).
BigInter m = new BigInteger(st, base); // st是字符串，base是st的进制.
a=cin.nextBigInteger(b); //以b进制读入一个大数赋值给a
c=a.toString(b); // 将大数a以b进制的方式赋给字符串c
a=newBigInteger(c, b); //把c 当做“b进制“转为十进制大数赋值给a
*/
计算几何
链接：https://ac.nowcoder.com/acm/contest/1112/J
来源：牛客网
Bobo 有一个三角形和一个矩形，他想求他们交的面积。
具体地，三角形和矩形由 8 个整数 x1,y1,x2,y2,x3,y3,x4,y4x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4x1,y1,x2,y2,x3,y3,x4,y4
描述。
表示三角形的顶点坐标是 (x1,y1),(x1,y2),(x2,y1)(x_1,
y_1), (x_1, y_2), (x_2, y_1)(x1,y1),(x1,y2),(x2,y1)，
矩形的顶点坐标是 (x3,y3),(x3,y4),(x4,y4),(x4,y3)(x_3,
y_3), (x_3, y_4), (x_4, y_4), (x_4, y_3)(x3,y3),(x3,y4),(x4,y4),(x4,y3)
把三角形的顶点里在矩形里面的点放进数组；
把矩形的顶点里在三角形里面的点放进数组；
把三角形三条边和矩形四条边的交点放进数组（规范相交）；
对这个数组去重并求凸包然后求凸包面积就是答案。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e3+10;
double eps=1e-8;
double pi=acos(-1);
struct Point{
double x,y;
Point(double x=0,double y=0):x(x),y(y){};
};
typedef Point Vector;
Vector operator +(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator -(Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator *(Vector A,double B){return Vector(A.x*B,A.y*B);}
Vector operator /(Vector A,double B){return Vector(A.x/B,A.y/B);}
int dcmp(double x){
if(fabs(x)<eps)return 0;
return x<0?-1:1;
}
bool operator<(const Point&a,const Point&b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
bool operator == (const Point &a,const Point &b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}
double Length(Vector A){return sqrt(Dot(A,A));}
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}
double Angle(Vector A) {return atan2(A.y, A.x);}
struct Circle{ //圆
Point c;
double r;
Circle(Point c = Point(0, 0), double r = 0):c(c),r(r){}
Point point(double a){
return Point(c.x+cos(a)*r,c.y+sin(a)*r);
}
};
double dis(Point A,Point B){
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
int circle_circle(Circle C1,Circle C2,vector<Point>&sol){//返回圆与圆的交点个数
double d=Length(C1.c-C2.c);
if(dcmp(d)==0){
if(dcmp(C1.r-C2.r)==0)return -1;
return 0;
}
if(dcmp(C1.r+C2.r-d)<0)return 0;
if(dcmp(fabs(C1.r-C2.r)-d)>0)return 0;
double a=Angle(C2.c-C1.c);
double da=acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*d*C1.r));
Point p1=C1.point(a-da),p2=C1.point(a+da);
sol.push_back(p1);
if(p1==p2)return 1;
sol.push_back(p2);
return 2;
}
Point line_point(Point p,Vector v,Point q,Vector w){//直线交点
Vector u=p-q;
double t=Cross(w,u)/Cross(v,w);
return p+v*t;
}
bool onsegment(Point p,Point a1,Point a2){
if(p==a1||p==a2)return true;
return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;
}
bool segmentcross(Point a1,Point a2,Point b1,Point b2){
double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),
c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
Point line_line(Point A,Point B,Point C,Vector D){//线段交点
if(segmentcross(A,B,C,D)){
return line_point(A,B-A,C,D-C);
}
return Point(123.456,0);
}
int tubao(Point *p,int n,Point *ch){
sort(p,p+n);
n=unique(p,p+n)-p;
int m=0;
for(int i=0;i<n;i++){
while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--){
while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
ch[m++]=p[i];
}
if(n>1)m--;
return m;
}
double tubaos(Point *p,int n){
double area=0;
for(int i=1;i<n-1;i++){
area+=Cross(p[i]-p[0],p[i+1]-p[0]);
}
return area/2;
}
int intubao(Point *ch,int n,Point p){
Vector A,B;
int flag=0;
for(int i=0;i<n;i++){
A=ch[(i+1)%n]-ch[i];
B=p-ch[i];
if(onsegment(p,ch[i],ch[(i+1)%n])){
flag=-1;
break;
}
else if(Cross(A,B)>0){
flag++;
}
}
if(flag==-1||flag==n)return 1;
return 0;
}
double x[N],y[N];
Point p[N],q[N],ch[N],ans[N];
int main(){
while(~scanf("%lf%lf",&x[1],&y[1])){
scanf("%lf%lf",&x[2],&y[2]);
scanf("%lf%lf",&x[3],&y[3]);
scanf("%lf%lf",&x[4],&y[4]);
int n=0;
p[n++]=Point(x[3],y[3]);
p[n++]=Point(x[4],y[3]);
p[n++]=Point(x[4],y[4]);
p[n++]=Point(x[3],y[4]);
int m=0;
q[m++]=Point(x[1],y[1]);
q[m++]=Point(x[1],y[2]);
q[m++]=Point(x[2],y[1]);
tubao(q,m,ch);
int cnt=0;
for(int i=0;i<n;i++){
if(intubao(ch,m,p[i])){
ans[cnt++]=p[i];
}
}
for(int i=0;i<m;i++){
if(intubao(p,n,q[i])){
ans[cnt++]=q[i];
}
}
p[n]=p[0];
q[m]=q[0];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
Point A=line_line(p[i],p[i+1],q[j],q[j+1]);
if(dcmp(A.x-123.456)!=0)ans[cnt++]=A;
}
}
int n1=tubao(ans,cnt,ch);
if(n1<=2)printf("%.8lf\n",0.0);
else printf("%.8lf\n",tubaos(ch,n1));
}
}
字符串双哈希
https://codeforc.es/contest/1200/problem/E
题意：给定一堆字符串，依次插入答案串尾部，每次删掉答案串的后缀 与 待插入串的前缀的最大匹配串
思路：hash匹配后缀和前缀，不断更新hash值
#define bug(x) cout<<#x<<" is "<<x<<endl
#define IO std::ios::sync_with_stdio(0)
#include <bits/stdc++.h>
#define iter ::iterator
#define pa pair<int,int>
using namespace std;
#define ll long long
#define mk make_pair
#define pb push_back
#define se second
#define fi first
#define ls o<<1
#define rs o<<1|1
const int N=1e6+5;
int n;
ll mod[5]={1000000009,998244353};
ll base[5]={666127,777131};
ll p[N][2];
ll h[N][2];
void init(){
for(int i=0;i<2;i++)p[0][i]=1;
for(int i=1;i<=N-2;i++){
for(int j=0;j<2;j++){
p[i][j]=p[i-1][j]*base[j]%mod[j];
}
}
}
ll cal(int l,int r,int t){
return (h[r][t]-h[l-1][t]*p[(r-l+1)][t]%mod[t]+mod[t])%mod[t];
}
ll get(char c){
if('a'<=c&&c<='z')return c-'a';
if('A'<=c&&c<='Z')return c-'A'+26;
if('0'<=c&&c<='9')return c-'0'+52;
}
string s,t;
int main(){
IO;
cin>>n;
cin>>s;
int pre=1;
init();
for(int g=1;g<n;g++){
cin>>t;
int ns=s.length();
for(int i=pre;i<=ns;i++){
ll c=get(s[i-1]);
for(int j=0;j<2;j++){
h[i][j]=(h[i-1][j]*base[j]%mod[j]+c)%mod[j];
}
}
int nt=t.length();
ll H[2]={0};
pre=ns+1;
int id=0;
for(int i=1;i<=nt;i++){
int f=0;
ll c=get(t[i-1]);
for(int j=0;j<2;j++){
H[j]=(H[j]*base[j]%mod[j]+c)%mod[j];
if(cal(ns-i+1,ns,j)==H[j])f++;
}
if(f==2){
id=i;
}
if(i==ns)break;
}
s+=t.substr(id,nt-id);
}
cout<<s<<endl;
}
/*
7
RAtONC14epz KfIenADgDKDci OMmOOQOc yVrfGLV49fW1 xntodZLM5 2f7LXdzX xIhm
5
I want to order pizza
*/
并查集、倍增
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 100005, mod = 1000000007;
int n, m, fa[maxn][18], ans;
int find(int x, int k) {
return fa[x][k] == x ? x : fa[x][k] = find(fa[x][k], k);
}
void merge(int x, int y, int k) {
x = find(x, k), y = find(y, k);
if(x != y) fa[x][k] = y;
}
int main() {
scanf("%d %d", &n, &m);
const int maxk = floor(log2(n));
for(int i = 1; i <= n; ++i)
for(int k = 0; k <= maxk; ++k)
fa[i][k] = i;
for(int i = 1, l1, r1, l2, r2; i <= m; ++i) {
scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
for(int k = maxk; ~k; --k)
if(l1+(1<<k)-1 <= r1) merge(l1, l2, k), l1 += 1<<k, l2 += 1<<k;
}
for(int k = maxk; k; --k)
for(int i = 1; i+(1<<k)-1 <= n; ++i) {
int pos = find(i, k);
merge(i, pos, k-1), merge(i+(1<<k-1), pos+(1<<k-1), k-1);
}
for(int i = 1; i <= n; ++i)
if(fa[i][0] == i) ans = !ans ? 9 : ans * 10ll % mod;
printf("%d\n", ans);
return 0;
}
笛卡尔树
#define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define bug(x) cout<<#x<<" is "<<x<<endl
#include <bits/stdc++.h>
#define iter ::iterator
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n;
ll a[N],b[N];
int st[N],ls[N],rs[N];
ll ans;
ll dfs(int u){
if(!u)return 0;
ll res=dfs(ls[u])+dfs(rs[u])+b[u];
ll res1=min(res,a[u]);
res1*=res1;
ans=max(ans,res1);
return res;
}
int main(){
IO;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
int h=0;
for(int i=1;i<=n;i++){
int k=h;
while(k>0&&a[st[k]]>a[i])k--;
if(k>0)rs[st[k]]=i;
if(k<h) ls[i]=st[k+1];
st[++k]=i;
h=k;
}
ans=0;
dfs(st[1]);
cout<<ans<<endl;
}
/*
11
9 3 7 1 8 12 10 20 15 18 5
*/
标签：return,Point,int,System,ACM,println,模板,out From： https://www.cnblogs.com/ccsu-kid/p/18226053