1>数星星
（复制自他人博客）
由于题目中给的数据是按y轴排序，我们只需构建x轴的树状数组，也就是说我们只需统计星星i之前一共有多少个x坐标小于或等于Xi的星星，这个数值也就是星星i的等级
又因为树状数组无法处理下标为0的元素（会死循环），所以要把每个x坐标+1
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int max(int a,int b) { return a>b ?a :b; } int n,mx; const int N=15003,M=33000; struct node { int x,y,xh; bool operator < (const node & o) const { return x!=o.x ?x<o.x :y<o.y; } }d[N]; int ans[N],cnt[N]; int tr[M]; int lowbit(int x) { return x&(-x); } void add(int pos) { while(pos<=mx) tr[pos]++,pos+=lowbit(pos); } int query(int pos) { int ans=0; while(pos>0) ans+=tr[pos],pos-=lowbit(pos); return ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&d[i].x ,&d[i].y ),d[i].xh =i, d[i].x ++,d[i].y ++,mx=max(mx,d[i].y ); sort(d+1,d+n+1); for(int i=1;i<=n;i++) { ans[d[i].xh ]=query(d[i].y ); add(d[i].y ); cnt[ans[d[i].xh ]]++; } for(int i=0;i<n;i++) printf("%d ",cnt[i]); return 0; }
2>花神游历各国
小清新线段树
有点像 普通线段树 + 剪枝
一般题面会有一个神奇的（暂且这么说）更改方式，而且一般没办法区间更新出值
这里是一个数的多次开方，可以发现，开方此时应该是有限的，<=1时不再变化
当区间最大值<=1时，整个区间都不再变化
#include<cstdio> #include<cstdlib> #include<cmath> #define ll long long using namespace std; ll max(ll a,ll b) { return a>b ?a :b; } const int N=100003; int n;ll d[N];int m; int root,cnt; struct node { int lson,rson; ll sum,mx; }tr[N<<1]; void updata(int rt) { tr[rt].sum =tr[tr[rt].lson ].sum +tr[tr[rt].rson ].sum ; tr[rt].mx = max(tr[tr[rt].lson ].mx ,tr[tr[rt].rson ].mx ); } void build(int &rt,int l,int r) { rt=++cnt; if(l==r) { tr[rt].sum =tr[rt].mx =d[l]; return ; } int mid=(l+r)>>1; build(tr[rt].lson ,l,mid); build(tr[rt].rson ,mid+1,r); updata(rt); } int ql,qr; void change(int rt,int l,int r) { if(tr[rt].mx <=1) return ; if(l==r ) { tr[rt].sum =tr[rt].mx =sqrt(tr[rt].sum ); return ; } int mid=(l+r)>>1; if(ql<=mid ) change(tr[rt].lson ,l,mid); if(qr> mid ) change(tr[rt].rson ,mid+1,r); updata(rt); } ll query(int rt,int l,int r) { if(ql<=l && qr>=r) return tr[rt].sum ; int mid=(l+r)>>1; if(qr<=mid) return query(tr[rt].lson ,l,mid); else if(ql>mid) query(tr[rt].rson ,mid+1,r); else return query(tr[rt].lson ,l,mid)+query(tr[rt].rson ,mid+1,r); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&d[i]); build(root,1,n); int op; scanf("%d",&m); while(m--) { scanf("%d%d%d",&op,&ql,&qr);//简化搜索次数，否则tle if(ql>qr) { int t=ql; ql=qr,qr=t; } if(op==1) printf("%lld ",query(1,1,n)); else change(1,1,n); } return 0; }