思路：
二维数点
离线后线段树维护

代码：

#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define int long long
#define lch p<<1
#define rch p<<1|1inline int in{int s=0,f=1;char x;for(x=getchar();x<'0'||x>'9';x=getchar())	if(x=='-')	f=-1;for( ;x>='0'&&x<='9';x=getchar())	s=(s*10)+(x&15);return f==1?s:-s;
}const int A=5e5+5;
int n,m;
struct Point{int x,y,val;
}pt[A];
struct Qurey{int x,y1,y2,id,opt;
}qur[A];
inline bool cmp1(const Point u,const Point v){return u.x<v.x;
}
inline bool cmp2(const Qurey u,const Qurey v){return u.x<v.x;
}int nw[A],tot,len;struct Tree{int l,r,val;
}tr[4*A];
int ans[A];inline void pushup(int p){tr[p].val=tr[lch].val+tr[rch].val;return;
}inline void build(int p,int l,int r){tr[p].l=l,tr[p].r=r;if(l==r){tr[p].val=0;return;}int mid=(l+r)>>1;build(lch,l,mid),build(rch,mid+1,r);pushup(p); return;
}inline void add(int p,int w,int val){if(tr[p].l==tr[p].r){tr[p].val+=val;return;}int mid=(tr[p].l+tr[p].r)>>1;if(w<=mid)	add(lch,w,val);else	add(rch,w,val);pushup(p);return;
}inline int qurey(int p,int l,int r){if(tr[p].l>=l&&tr[p].r<=r)	return tr[p].val;int ans=0;int mid=(tr[p].l+tr[p].r)>>1;if(l<=mid)	ans+=qurey(lch,l,r);if(r>=mid+1)	ans+=qurey(rch,l,r);pushup(p);return ans;
}inline void scan(){n=in,m=in;for(int i=1;i<=n;i++){pt[i].x=in,pt[i].y=in,pt[i].val=in;nw[++tot]=pt[i].y;}for(int i=1;i<=m;i++){int a=in,b=in,c=in,d=in;a--;qur[2*i-1].x=a,qur[2*i-1].y1=b,qur[2*i-1].y2=d,qur[2*i-1].id=i,qur[2*i-1].opt=-1;qur[2*i].x=c,qur[2*i].y1=b,qur[2*i].y2=d,qur[2*i].id=i,qur[2*i].opt=1;nw[++tot]=b,nw[++tot]=d;}sort(nw+1,nw+1+tot);len=unique(nw+1,nw+1+tot)-(nw+1);for(int i=1;i<=n;i++)pt[i].y=lower_bound(nw+1,nw+1+len,pt[i].y)-nw;for(int i=1;i<=2*m;i+=2){qur[i].y1=lower_bound(nw+1,nw+1+len,qur[i].y1)-nw;qur[i].y2=lower_bound(nw+1,nw+1+len,qur[i].y2)-nw;qur[i+1].y1=qur[i].y1,qur[i+1].y2=qur[i].y2;}sort(pt+1,pt+1+n,cmp1);sort(qur+1,qur+1+2*m,cmp2);return;
}inline void work(){build(1,1,len);int pos=1;for(int i=1;i<=2*m;i++){while(pos<=n&&pt[pos].x<=qur[i].x){add(1,pt[pos].y,pt[pos].val);pos++;}if(qur[i].opt==-1){ans[qur[i].id]-=qurey(1,qur[i].y1,qur[i].y2);}else{ans[qur[i].id]+=qurey(1,qur[i].y1,qur[i].y2);}}for(int i=1;i<=m;i++)	printf("%lld\n",ans[i]);return;
}signed main(){scan(); work();return 0;
}

思路：

因为是网格图，所以考虑染色将格子分类

发现奇偶行，奇偶列分别是不同的

那么有四种格子，考虑用四种颜色染色

(图)

发现题目中给的四种图形都有相同性质

每个图形必定包含四种颜色，并且红色和蓝色必定相邻

于是破环一个图形至少会破坏一种颜色

考虑最小割

对于一个图形，需要只连一条通路

发现黄色和蓝不直接相邻，绿色和红色不直接相邻，并且红色和蓝色必定相邻

于是考虑黄色连向红色连向蓝色连向绿色

(图)

将红蓝间的边权赋为红蓝点权的小值，黄红边权赋为 INF，蓝绿边权赋为 INF

源点向黄点连边，边权为黄点点权，绿点向汇点连边，边权为绿点点权

跑最小割即可

代码：

#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
#define in Read()
#define int long long
#define re register
#define S 0
#define T (n+1)inline char ch(){static char buf[1<<21],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}inline int in{int s=0,f=1;char x;for(x=ch();x<'0'||x>'9';x=ch())	if(x=='-')	f=-1;for( ;x>='0'&&x<='9';x=ch())	s=(s*10)+(x&15);return f==1?s:-s;
}const int A=2e5+5;
const int B=6e6+5;
const int INF=1e18;
int N,M,n;
int p1[A],p2[A];
int val[A];
tr1::unordered_map <int,int> ma;
inline int d(int x,int y){return (x-1)*max(N,M)+y;
}
int maxflow=0;
int head[A],tot_road=1;
struct Road{int nex,to,w;
}road[B];
inline void ljb(int x,int y,int w){road[++tot_road]={head[x],y,w};head[x]=tot_road;
}
int dep[A],sum[A];inline void scan(){N=in,M=in,n=in;for(re int i=1;i<=n;++i){int u=in,v=in;p1[i]=u,p2[i]=v,val[i]=in;ma.insert(pair<int,int>(d(u,v),i));}return;
}inline void red(int x,int y){if(x%4==0){if(x-1>=1&&ma.find(d(x-1,y))!=ma.end()){int u=ma[d(x,y)],v=ma[d(x-1,y)];ljb(u,v,min(val[u],val[v])),ljb(v,u,0);}}else{if(x+1<=N&&ma.find(d(x+1,y))!=ma.end()){int u=ma[d(x,y)],v=ma[d(x+1,y)];ljb(u,v,min(val[u],val[v])),ljb(v,u,0);}}return;
}
inline void blu(int x,int y){int u=ma[d(x,y)],v;if(y+1<=M&&ma.find(d(x,y+1))!=ma.end()){v=ma[d(x,y+1)];ljb(u,v,INF),ljb(v,u,0);}if(y-1>=1&&ma.find(d(x,y-1))!=ma.end()){v=ma[d(x,y-1)];ljb(u,v,INF),ljb(v,u,0);}if(x%4==2){if(x+1<=N&&ma.find(d(x+1,y))!=ma.end()){v=ma[d(x+1,y)];ljb(u,v,INF),ljb(v,u,0);}}else{if(x-1>=1&&ma.find(d(x-1,y))!=ma.end()){v=ma[d(x-1,y)];ljb(u,v,INF),ljb(v,u,0);}}return;
}
inline void yel(int x,int y){int u=ma[d(x,y)],v;ljb(S,u,val[u]),ljb(u,S,0);if(y+1<=M&&ma.find(d(x,y+1))!=ma.end()){v=ma[d(x,y+1)];ljb(u,v,INF),ljb(v,u,0);}if(y-1>=1&&ma.find(d(x,y-1))!=ma.end()){v=ma[d(x,y-1)];ljb(u,v,INF),ljb(v,u,0);}if(x%4==0){if(x+1<=N&&ma.find(d(x+1,y))!=ma.end()){v=ma[d(x+1,y)];ljb(u,v,INF),ljb(v,u,0);}}else{if(x-1>=1&&ma.find(d(x-1,y))!=ma.end()){v=ma[d(x-1,y)];ljb(u,v,INF),ljb(v,u,0);}}return;
}
inline void gre(int x,int y){int u=ma[d(x,y)];ljb(u,T,val[u]),ljb(T,u,0);return;
}inline void build(){for(re int now=1;now<=n;++now){int i=p1[now],j=p2[now];if(ma.find(d(i,j))==ma.end())	continue;if(i%4==0){if(j%2==0){red(i,j);}else{yel(i,j);}}else if(i%4==1){if(j%2==0){yel(i,j);}else{red(i,j);}}else if(i%4==2){if(j%2==0){gre(i,j);}else{blu(i,j);}}else{if(j%2==0){blu(i,j);}else{gre(i,j);}}}return;
}inline void BFS(){memset(dep,-1,sizeof(dep));memset(sum,0,sizeof(sum));queue <int> q;dep[T]=0,sum[dep[T]]++;q.push(T);while(!q.empty()){int x=q.front();q.pop();for(re int y=head[x];y;y=road[y].nex){int z=road[y].to;if(dep[z]!=-1)	continue;dep[z]=dep[x]+1,sum[dep[z]]++;q.push(z);}}return;
}inline int DFS(int x,int flow){if(x==T){maxflow+=flow;return flow;}int used=0;for(re int y=head[x];y;y=road[y].nex){int z=road[y].to,w=road[y].w;if(w&&dep[z]==dep[x]-1){int after=DFS(z,min(w,flow-used));if(after){used+=after;road[y].w-=after;road[y^1].w+=after;}}if(flow==used)	return used;}if(!--sum[dep[x]])	dep[T]=T+1;sum[++dep[x]]++;return used;
}inline void ISAP(){maxflow=0;BFS();while(dep[T]<=T)	DFS(S,INF);return;
}inline void print(){printf("%lld\n",maxflow);return;
}signed main(){scan();build();ISAP();print();return 0;
}

思路：
可以建成一棵二叉树
然后在树上 dp，合并左右子树方案数

代码：

#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define int long longinline int in{int s=0,f=1;char x;for(x=getchar();x<'0'||x>'9';x=getchar())	if(x=='-')	f=-1;for( ;x>='0'&&x<='9';x=getchar())	s=(s*10)+(x&15);return f==1?s:-s;
}const int A=1e3+5;
const int mod=1e9+7;
int n;
char a[A];
int f[A][A],g[A][A],t[A][A],sz[A];
int c[A][A];
int res=0;inline void DFS(int x){sz[x]=1,f[x][1]=1;for(int i=2*x;i<=min(n,2*x+1);i++){DFS(i);sz[x]+=sz[i];for(int j=1;j<=sz[x];j++)for(int k=0;k<j;k++){if(a[i]=='>'){t[x][j]=(t[x][j]+c[j-1][k]*c[sz[x]-j][sz[i]-k]%mod*f[i][k]%mod*f[x][j-k])%mod;}else{t[x][j]=(t[x][j]+c[j-1][k]*c[sz[x]-j][sz[i]-k]%mod*g[i][k+1]%mod*f[x][j-k])%mod;}}for(int j=1;j<=sz[x];j++)	f[x][j]=t[x][j],t[x][j]=0;}for(int i=sz[x];i;i--)	g[x][i]=(g[x][i+1]+f[x][i])%mod;for(int i=1;i<=sz[x];i++)	f[x][i]=(f[x][i]+f[x][i-1])%mod;return;
}signed main(){n=in;scanf("%s",a+2);c[0][0]=1;for(int i=1;i<=n;i++){c[i][0]=1;for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}DFS(1);printf("%lld\n",f[1][sz[1]]);return 0;
}