#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
const int N=2e5+5;
int n,T,op[N],L[N],R[N],t[N];
ll c[2];
void ins(int x,int v){
for(;x <= n + n;x += x & -x)t[x] += v;
}
int sum(int x){
int res = 0;
for(;x;x -= x & -x)res += t[x];
return res;
}
void work(int x,int y){
int cur = sum(x) & 1,cnt = 1 + sum(y) - sum(x);//start color & number of segs
c[cur] += (cnt + 1) / 2,c[cur ^ 1] += cnt / 2;
}
bool vis[N];
struct node{
int pos,val,id;
bool operator <(const node &a)const{return pos < a.pos;}
};
set <node> S;
void check(int x,int y){
auto cur = S.lower_bound({x,0,0});
vector <node> v;
while(cur != S.end()){
if((*cur).pos > y)break;
v.pb(*cur);cur++;
}
if(v.empty())return;
sort(v.begin(),v.end(),[](node x,node y){return x.id < y.id;});
int id = v[0].id;
for(auto t : v)if(t.id != id){//合并
if(!vis[t.id]){
vis[t.id] = 1,c[t.val]--;
S.erase({L[t.id],0,0}),S.erase({R[t.id] + 1,0,0});
}
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> T;
rep(i,1,n){
int x,y,X,Y;
cin >> x >> y >> X >> Y;
op[x] = 1,L[x] = y,R[x] = Y - 1;
op[X] = -1,L[X] = y,R[X] = Y - 1;
}
rep(i,1,2*n){
ins(L[i],op[i]),ins(R[i] + 1,op[i]);
work(L[i],R[i]);
check(L[i],R[i] + 1);
if(op[i] == 1){
if(sum(L[i]) == sum(R[i])){//新连通块
int w = (sum(L[i]) & 1) ^ 1;
c[w]++;
S.insert({L[i],w,i}),S.insert({R[i] + 1,w,i});
}
}else{
//减去多算的颜色
c[sum(L[i] - 1) & 1]--,c[sum(R[i] + 1) & 1]--;
auto cur = S.lower_bound({L[i],0,0});
if(cur != S.end() && (*cur).pos == L[i]){
S.erase(cur);S.erase({R[i] + 1,0,0});
}
}
}
c[0]++;
if(T == 1)cout << c[0] + c[1] << 'n';
else cout << c[0] << ' ' << c[1] << 'n';
return 0;
}
T2
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N= 1e6 + 5;
int n,q,pri[N],tot,flg;
bool vis[N];
ll a[N],s[N];
map <ll,int,greater<ll> > mp;
vector <ll> P;
ll gcd(ll x,ll y){return !y ? x : gcd(y,x % y);}
int main(){
n = read();
rep(i,2,1000000){
if(!vis[i])pri[++tot] = i;
for(int j = 1;j <= tot && i * pri[j] <= 1000000;j++){
vis[i * pri[j]] = 1;
if(i % pri[j] == 0)break;
}
}
rep(i,1,n)a[i] = read();
rep(i,1,n)s[i] = s[i-1] + a[i];
ll S = s[n];
rep(i,1,tot){
if(S % pri[i] == 0){
while(S % pri[i] == 0)S /= pri[i];
P.pb(pri[i]);
}
}
ll x = sqrt(S);
if(x > 1 && x * x == S)P.pb(S/x),flg = 1;
rep(i,1,n-1){
s[i] = gcd(s[i],s[n]);
mp[s[i]]++;
if(!flg){
ll x = s[i];
for(ll p : P)while(x % p == 0)x /= p;
if(x > 1e6 && flg != 1){
if(x < S){
P.pb(x),P.pb(S/x),flg = 1;
}else flg = 2;
}
}
}
if(flg == 2)P.pb(S);
for(ll p : P){
for(auto it = mp.begin();it != mp.end();it++){
if(it->fi % p == 0)mp[it->fi / p] += it->se;
}
}
q = read();
while(q--){
ll k = read();
if(s[n] % k != 0){
puts("-1");
continue;
}
ll ans = s[n] / k + n - 2 - 2 * mp[k];
printf("%lldn",ans);
}
return 0;
}
T3
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=1e5+5,P = 1e9+7;
int num[2048];
const int A[4] = {
1<<1|1<<2|1<<4|1<<5,1<<2|1<<3|1<<5|1<<6,
1<<4|1<<5|1<<7|1<<8,1<<5|1<<6|1<<8|1<<9
};
int sta4(int a,int b,int c,int d){return 1<<a|1<<b|1<<c|1<<d;}
int sta2(int a,int b){return 1<<a|1<<b;}
bool insq(int S,int c,int sq){
if((S & sq) != S)return 0;
if(num[S] != c)return 0;
if(find(A,A+4,sq) == A+4)return 0;
return 1;
}
bool line(int a,int b){
if(a != b)return 0;
if(a % 9 == 0){//是否列相邻
a /= 9;
return (a & (a-1)) == 0;
}
if(a % 3 == 0){//行相邻
a /= 3;
if(a & a-1)return 0;
if(a == 1<<3 || a == 1<<6)return 0;
return 1;
}
return 0;
}
struct S{
int a3,a2,a1,a0;
bool operator < (const S &x)const{
return a3 < x.a3 || a3 == x.a3 && (a2 < x.a2 || a2 == x.a2 && (a1 < x.a1 || a1 == x.a1 && a0 < x.a0));
}
};
char s[N];
int n,a[N];
inline int c(char ch){return ch - '0';}
map <S,int> f,g;
void solve(){
scanf("%s",s+1);
int n = 0;
while(s[n+1])n++;
rep(i,1,n)a[i] = s[i] - '0';
f.clear();
f[(S){-1,-1,-1,0}] = 1;
rep(i,1,n){
g.clear();
for(auto &pre : f){
S o = pre.fi;
rep(x,1,9){
S nxt;
nxt.a3 = o.a2 | 1 << x;
nxt.a2 = o.a1 | 1 << x;
nxt.a1 = o.a0 | 1 << x;
nxt.a0 = -1;
if(o.a3 != -1 && insq(o.a3 | 1 << x,4,sta4(a[i-3],a[i-2],a[i-1],a[i])))nxt.a0 = 0;
if(nxt.a2 != -1 && line(nxt.a2,sta2(a[i-1],a[i])))nxt.a0 = 0;
if(nxt.a1 == (1<<a[i]))nxt.a0 = 0;
if(nxt.a3 != -1 && (i == n || !insq(nxt.a3,3,sta4(a[i-2],a[i-1],a[i],a[i+1]))))nxt.a3 = -1;
if(nxt.a2 != -1 && (i >= n-1 || !insq(nxt.a2,2,sta4(a[i-1],a[i],a[i+1],a[i+2]))))nxt.a2 = -1;
if(nxt.a0 != -1 || nxt.a1 != -1 || nxt.a2 != -1 || nxt.a3 != -1){
g[nxt] = (g[nxt] + pre.se) % P;
}
}
}
f = g;
}
ll ans = 0;
for(auto &i : f)if(i.fi.a0 == 0)ans = (ans + i.se) % P;
cout << ans << 'n';
}
int main(){
rep(i,1,2047)num[i] = num[i>>1] + (i&1);
int T = read();
while(T--)solve();
return 0;
}【竞赛报名/项目咨询+微信：mollywei007】
