发现线段树根本不会写，所以想要完成洛谷官方题单来稍微提升一下...
持续更新ing
[========]
P3870 [TJOI2009] 开关
明确了写线段树要思考的几个点
1.如何update，即如何合并子节点的信息，这里就是直接将子节点的灯的数量相加即可
2.如何modify，即如何根据tag修改该节点的值，这里就是节点长度-灯的数量就行
还有如何下传tag，这里直接^就行
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<assert.h>
using namespace std;
#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
struct Node{
int add;
int x;
}seg[N*4];
Node operator+(const Node& a,const Node& b){
Node c;
c.x=a.x+b.x;
return c;
}
void settag(int u,int l,int r,int add){
if(add==1){
int len=r-l+1;
seg[u].x=len-seg[u].x;
seg[u].add^=add;
}
}
void pushdown(int u,int l,int r){
int mid=l+r>>1;
settag(u*2,l,mid,seg[u].add);
settag(u*2+1,mid+1,r,seg[u].add);
seg[u].add=0;
}
void update(int u){
seg[u].x=seg[u*2].x+seg[u*2+1].x;
}
void modify(int u,int l,int r,int ql,int qr,int add){
assert(l<=ql and qr<=r);
if(l==ql and r==qr)settag(u,l,r,add);
else{
pushdown(u,l,r);
int mid=l+r>>1;
if(qr<=mid)modify(u*2,l,mid,ql,qr,add);
else if(ql>=mid+1)modify(u*2+1,mid+1,r,ql,qr,add);
else{
modify(u*2,l,mid,ql,mid,add);
modify(u*2+1,mid+1,r,mid+1,qr,add);
}
update(u);
}
}
Node query(int u,int l,int r,int ql,int qr){
assert(l<=ql and qr<=r);
if(l==ql and r==qr)return seg[u];
else{
pushdown(u,l,r);
int mid=l+r>>1;
if(qr<=mid)return query(u*2,l,mid,ql,qr);
else if(ql>=mid+1)return query(u*2+1,mid+1,r,ql,qr);
else{
auto L=query(u*2,l,mid,ql,mid);
auto R=query(u*2+1,mid+1,r,mid+1,qr);
Node res=L+R;
return res;
}
update(u);
}
}
void solve(){
int n,m;
cin>>n>>m;
while(m--){
int c,a,b;
cin>>c>>a>>b;
if(c==0){
modify(1,1,n,a,b,1);
}else{
cout<<query(1,1,n,a,b).x<<endl;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin>>T;
while(T--){
solve();
}
return 0;
}
[========]
P1438 无聊的数列
区间加等差数列，单点求和
直接转化为差分，区间加就行
用树状数组也能做
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<assert.h>
using namespace std;
#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
LL a[N],b[N];
struct Node{
LL add;
LL x;
}seg[N*4];
void update(int u){
seg[u].x=seg[u*2].x+seg[u*2+1].x;
}
void build(int u,int l,int r){
assert(l<=r);
if(l==r)seg[u].x=b[l];
else{
int mid=l+r>>1;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
update(u);
}
}
void settag(int u,int l,int r,LL add){
int len=r-l+1;
seg[u].x+=len*add;
seg[u].add+=add;
}
void pushdown(int u,int l,int r){
int mid=l+r>>1;
settag(u*2,l,mid,seg[u].add);
settag(u*2+1,mid+1,r,seg[u].add);
seg[u].add=0;
}
void modify(int u,int l,int r,int ql,int qr,LL add){
assert(l<=ql and qr<=r);
if(l==ql and r==qr)settag(u,l,r,add);
else{
pushdown(u,l,r);
int mid=l+r>>1;
if(qr<=mid)modify(u*2,l,mid,ql,qr,add);
else if(ql>=mid+1)modify(u*2+1,mid+1,r,ql,qr,add);
else{
modify(u*2,l,mid,ql,mid,add);
modify(u*2+1,mid+1,r,mid+1,qr,add);
}
update(u);
}
}
Node query(int u,int l,int r,int ql,int qr){
assert(l<=ql and qr<=r);
if(l==ql and r==qr)return seg[u];
else{
pushdown(u,l,r);
int mid=l+r>>1;
if(qr<=mid)return query(u*2,l,mid,ql,qr);
else if(ql>=mid+1)return query(u*2+1,mid+1,r,ql,qr);
else{
Node res;
auto L=query(u*2,l,mid,ql,mid);
auto R=query(u*2+1,mid+1,r,mid+1,qr);
res.x=L.x+R.x;
return res;
}
update(u);
}
}
void solve(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
build(1,1,n);
while(m--){
int op;cin>>op;
if(op==1){
LL l,r,k,d;
cin>>l>>r>>k>>d;
modify(1,1,n,l,l,k);
if(l+1<=r)modify(1,1,n,l+1,r,d);
if(r+1<=n)modify(1,1,n,r+1,r+1,-(k+(r-l)*d));
}else{
int p;cin>>p;
cout<<query(1,1,n,1,p).x<<endl;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin>>T;
while(T--){
solve();
}
return 0;
}