{"id":1006,"date":"2021-11-27T16:32:40","date_gmt":"2021-11-27T08:32:40","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=1006"},"modified":"2021-11-27T16:35:01","modified_gmt":"2021-11-27T08:35:01","slug":"lp1438-%e6%97%a0%e8%81%8a%e7%9a%84%e6%95%b0%e5%88%97","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2021\/11\/27\/lp1438-%e6%97%a0%e8%81%8a%e7%9a%84%e6%95%b0%e5%88%97\/","title":{"rendered":"lp1438 \u65e0\u804a\u7684\u6570\u5217"},"content":{"rendered":"\n

\u533a\u95f4\u52a0\u4e0a\u4e00\u4e2a\u7b49\u5dee\u6570\u5217\u8fd9\u4ef6\u4e8b\u60c5\u5176\u5b9e\u5e76\u4e0d\u597d\u7ef4\u62a4\u3002\u4f46\u65e2\u7136\u662f\u5355\u70b9\u67e5\u8be2\uff0c\u90a3\u5c31\u53ef\u4ee5\u8003\u8651\u5dee\u5206\u3002
\u6211\u4eec\u8003\u8651\u5c06\u6570\u5217\u5dee\u5206\uff0c\u7ef4\u62a4\u4e00\u4e2a\u5dee\u5206\u6570\u5217\u3002\u4e8e\u662f\u533a\u95f4 [l,r] \u52a0\u4e0a\u7b49\u5dee\u6570\u5217 {K,D}\uff0c\u5c31\u53d8\u6210\u4e86\u4e09\u4e2a\u64cd\u4f5c\uff1a
\u70b9 l \u52a0\u4e0a K
\u533a\u95f4 [l+1,r] \u52a0\u4e0a D
\u70b9 r+1 \u51cf\u53bb K+(r-l)*D
\u5bf9\u4e8e\u6bcf\u4e2a\u67e5\u8be2\u6c42\u524d\u7f00\u548c\u5373\u53ef\u3002<\/p>\n\n\n\n

#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\ntypedef long long ll;\n\nconst int N=100005;\nint n,m;\nll a[N];\nll val[N<<2],tag[N<<2];\ninline void pshd(int L,int R,int X){\n\tint MID=(L+R)>>1;\n\ttag[X<<1]+=tag[X];tag[X<<1|1]+=tag[X];\n\tval[X<<1]+=tag[X]*(MID-L+1);val[X<<1|1]+=tag[X]*(R-MID);\n\ttag[X]=0;\n}\ninline void updt(int X){\n\tval[X]=val[X<<1]+val[X<<1|1];\n}\nll qry(int L,int R,int A,int B,int X){\n\tif(A<=L&&B>=R){\n\t\treturn val[X];\n\t}\n\tint MID=(L+R)>>1;ll ret=0;\n\tpshd(L,R,X);\n\tif(A<=MID){\n\t\tret+=qry(L,MID,A,B,X<<1);\n\t}\n\tif(B>MID){\n\t\tret+=qry(MID+1,R,A,B,X<<1|1);\n\t}\n\treturn ret;\n}\nvoid mdf(int L,int R,int A,int B,int X,ll V){\n\tif(A<=L&&B>=R){\n\t\ttag[X]+=V;\n\t\tval[X]+=V*(R-L+1);\n\t\treturn;\n\t}\n\tint MID=(L+R)>>1;\n\tpshd(L,R,X);\n\tif(A<=MID){\n\t\tmdf(L,MID,A,B,X<<1,V);\n\t}\n\tif(B>MID){\n\t\tmdf(MID+1,R,A,B,X<<1|1,V);\n\t}\n\tupdt(X);\n}\nvoid build(int L,int R,int X){\n\tif(L==R){\n\t\tval[X]=a[L];\n\t\treturn;\n\t}\n\tint MID=(L+R)>>1;\n\tbuild(L,MID,X<<1);\n\tbuild(MID+1,R,X<<1|1);\n\tupdt(X);\n}\ninline void chg(int L,int R,ll V){\n\tif(L>R||L<1||R>n){\n\t\treturn;\n\t}\n\tmdf(1,n,L,R,1,V);\n}\ninline void init(){\n\tscanf(\"%d%d\",&n,&m);\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%lld\",&a[i]);\n\t}\n\tfor(int i=n;i>1;--i){\n\t\ta[i]-=a[i-1];\n\t}\n\tbuild(1,n,1);\n\tll opt,l,r,k,d,p;\n\tfor(int i=1;i<=m;++i){\n\t\tscanf(\"%lld\",&opt);\n\t\tif(opt==1){\n\t\t\tscanf(\"%lld%lld%lld%lld\",&l,&r,&k,&d);\n\t\t\tchg(l,l,k);chg(l+1,r,d);chg(r+1,r+1,-(k+d*(r-l)));\n\t\t}else{\n\t\t\tscanf(\"%lld\",&p);\n\t\t\tprintf(\"%lld\\n\",qry(1,n,1,p,1));\n\t\t}\n\t}\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u533a\u95f4\u52a0\u4e0a\u4e00\u4e2a\u7b49\u5dee\u6570\u5217\u8fd9\u4ef6\u4e8b\u60c5\u5176\u5b9e\u5e76\u4e0d\u597d\u7ef4\u62a4\u3002\u4f46\u65e2\u7136\u662f\u5355\u70b9\u67e5\u8be2\uff0c\u90a3\u5c31\u53ef\u4ee5\u8003\u8651\u5dee\u5206\u3002\u6211\u4eec\u8003\u8651\u5c06\u6570\u5217\u5dee\u5206\uff0c\u7ef4\u62a4\u4e00\u4e2a\u5dee … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201clp1438 \u65e0\u804a\u7684\u6570\u5217\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[52,43,8,6,48,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/1006"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=1006"}],"version-history":[{"count":2,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/1006\/revisions"}],"predecessor-version":[{"id":1011,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/1006\/revisions\/1011"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=1006"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=1006"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=1006"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}