2018年湖南省省赛 H题-千万不要用树套树

2019-04-13 20:48发布

站内文章 / 模拟电子
10927 0 1588

题目：点击打开链接

题意：略。

分析：用总线段条数减去左端点大于l和右端点小于l的线段数（这两种情况不会有重合），线段树单点更新，区间求和。

代码：

#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #pragma comment(linker, "/STACK:102400000,102400000") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define pt(a) cout<=a;i--) #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) #define ll long long #define ull unsigned long long #define pb push_back #define mp make_pair #define inf 0x3f3f3f3f #define eps 1e-10 #define PI acos(-1.0) typedef pair PII; const ll mod = 1e9+7; const int N = 1e5+10; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int n,q,s1[4*N],s2[4*N]; void up(int l,int r,int id,int x,int tp[]) { if(l==r) { tp[id]++; return ; } int m=(l+r)/2; if(x<=m) up(l,m,2*id,x,tp); else up(m+1,r,2*id+1,x,tp); tp[id]=tp[2*id]+tp[2*id+1]; } int qy(int l,int r,int ql,int qr,int id,int tp[]) { if(ql>qr) return 0; if(ql<=l&&qr>=r) return tp[id]; int m=(l+r)/2,res=0; if(ql<=m) res+=qy(l,m,ql,qr,2*id,tp); if(qr>m) res+=qy(m+1,r,ql,qr,2*id+1,tp); return res; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); while(scanf("%d%d",&n,&q)!=EOF) {///注意EOF否则会输出超限 mst(s1,0),mst(s2,0); int cnt=0; while(q--) { int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op==1) { cnt++,up(1,n,1,l,s1),up(1,n,1,r,s2); }else printf("%d ",cnt-qy(1,n,l+1,n,1,s1)-qy(1,n,1,r-1,1,s2)); } } return 0; }  

热门文章