segment tree
监视任务
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define lson le,mid,root<<1
#define rson mid+1,rig,root<<1|1
using namespace std;
struct node{
int l,r,k;
bool operator<(const node &b) const{
return r<b.r;
}
}a[1000005];
int sum[500005<<2];
int book[500005];
void pushup(int root)
{
sum[root]=sum[root<<1]+sum[root<<1|1];
}
void build(int le,int rig,int root){
if (le==rig) {
sum[root]=0;
return;
}
int mid=(le+rig)>>1;
build(lson);
build(rson);
pushup(root);
}
int query(int l,int r,int le,int rig,int root){
if (l<=le&&r>=rig) return sum[root];
int re=0;
int mid=(le+rig)>>1;
if (l<=mid) re+=query(l,r,lson);
if (r>mid) re+=query(l,r,rson);
return re;
}
void update(int pos,int le,int rig,int root){
if (le==rig) {
sum[root]=1;
return;
}
int mid=(le+rig)>>1;
if(pos<=mid) {
update(pos,lson);
}
else {
update(pos,rson);
}
pushup(root);
}
int main(){
int n,m,ans;
while (scanf("%d%d",&n,&m)!=EOF){
ans=0;
memset(book,0,sizeof(book));
for (int i=0;i<m;i++){
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].k);
}
build(1,n,1);
sort(a,a+m);
for (int i=0;i<m;i++){
int pos=a[i].r;
int cnt=query(a[i].l,a[i].r,1,n,1);
while (cnt<a[i].k){
while (book[pos]) pos--;
book[pos]=1;
update(pos,1,n,1);
ans++;
cnt++;
}
}
printf("%d\n",ans);
}
return 0;
}
contest
#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=200010;
int c[maxn];
int n;
int a[maxn];
int cnt;
struct node2{
int x,y,z;
}peo[200100];
struct node{
int id;
ll num;
}r[maxn];
int cmp(node x,node y)
{
if (x.num!=y.num)
return x.num<y.num;
else
return x.id<y.id;
}
int lowbit(int x){
return x&(-x);
}
void add(int i,int value){
while (i<=n){
c[i]+=value;
i+=lowbit(i);
}
}
int sum(int i){
int sum=0;
while (i>=1){
sum+=c[i];
i-=lowbit(i);
}
return sum;
}
int main(){
int t,i,tmp;
ll ans;
ans=0;
while (scanf("%d",&n)!=EOF){
for (int i=1;i<=n;i++)
{
scanf("%d%d%d",&peo[i].x,&peo[i].y,&peo[i].z);
}
memset(c,0,sizeof(c));
memset(r,0,sizeof(r));
for (int i=1;i<=n;i++)
{
r[i].num=peo[i].y;
r[i].id=peo[i].x;
}
sort(r+1,r+n+1,cmp);
for (int j=1;j<=n;j++)
{
add(r[j].id,1);
ans+=j-sum(r[j].id);
}
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++){
r[i].num=peo[i].z;
r[i].id=peo[i].x;
}
sort(r+1,r+n+1,cmp);
for (int j=1;j<=n;j++){
add(r[j].id,1);
ans+=j-sum(r[j].id);
}
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++)
{r[i].num=peo[i].z;
r[i].id=peo[i].y;
}
sort(r+1,r+n+1,cmp);
for (int j=1;j<=n;j++)
{
add(r[j].id,1);
ans+=j-sum(r[j].id);
}
printf("%lld\n",ans/2);
}
return 0;
}
sum
#include<cstdio>
#include<cstring>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define LL long long
#define mod 1000000007
using namespace std;
const int N=1e5+10;
const int M=1e9+10;
int num[N];
int bit[35][N];
int n,m,k,u,v,op,t;
LL ans;
LL quick_pow(LL x,int n)
{
LL res=1;
while(n)
{
if(n&1) res=(res*x)%mod;
x=(x*x)%mod;
n>>=1;
}
return res;
}
void add(int i,int x,int pos)
{
while(i<=n)
{
bit[pos][i]+=x;
i+=i&-i;
}
return ;
}
int sum(int i,int pos)
{
int s=0;
while(i>0)
{
s+=bit[pos][i];
i-=i&-i;
}
return s;
}
int main()
{
scanf("%d",&n);
clr(bit);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
k=0;
t=num[i];
while(t)
{
if(t&1) add(i,1,k);
t>>=1;
k++;
}
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&op,&u,&v);
if(op==1)
{
k=0;
t=num[u];
while(t)
{
if(t&1) add(u,-1,k);
t>>=1;
k++;
}
num[u]=t=v;
k=0;
while(t)
{
if(t&1) add(u,1,k);
t>>=1;
k++;
}
}
if(op==2)
{
ans=0;
for(k=0;k<=32;k++)
{
ans=(ans+(quick_pow(2,sum(v,k)-sum(u-1,k))-1)*quick_pow(2,k)%mod)%mod;
}
printf("%lld\n",ans);
}
}
return 0;
}
butterfly
#include<cstdio>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define lson rt<<1
#define rson rt<<1|1
const int INF = 1e9 + 7;
const int A = 2e3 + 10;
class TNode{
public:
int l,r,Mx;
};
class Seg_Tree{
public:
TNode Tree[A<<3];
void push_up(int rt){
Tree[rt].Mx=max(Tree[lson].Mx,Tree[rson].Mx);
}
void build_Tree(int rt,int l,int r){
Tree[rt].l=l;
Tree[rt].r=r;
Tree[rt].Mx=-INF;
if (l==r) return;
int mid=(l+r)>>1;
build_Tree(lson,l,mid);
build_Tree(rson,mid+1,r);
push_up(rt);
}
void update(int rt,int pos,int add){
int l=Tree[rt].l,r=Tree[rt].r;
if (l==r) {
Tree[rt].Mx=add;
return;
}
int mid=(l+r)>>1;
if (pos<=mid) update(lson,pos,add);
else update(rson,pos,add);
push_up(rt);
}
int query(int rt,int st,int ed,int v){
int l=Tree[rt].l,r=Tree[rt].r;
if (l==r) return l;
int res=0;
if(st<=l&&r<=ed){
if (Tree[rson].Mx>=v) res=query(rson,st,ed,v);
else if (Tree[lson].Mx>=v) res=query(lson,st,ed,v);
return res;
}
int mid=(l+r)>>1;
if(ed>mid&&Tree[rson].Mx>=v) res=query(rson,st,ed,v);
if (res) return res;
if (st<=mid&&Tree[lson].Mx>=v) res=query(lson,st,ed,v);
return res;
}
}T1,T2;
char s[A][A];
int dp[3][A][A];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%s",s[i]+1);
for (int i=n;i>=1;i--)
for (int j=1;j<=m;j++)
{
if (s[i][j]!='X') continue;
dp[0][i][j]=dp[0][i+1][j-1]+1;
dp[1][i][j]=dp[1][i+1][j]+1;
dp[2][i][j]=dp[2][i+1][j+1]+1;
}
int ans=0;
for (int i=1;i<=n;i++){
T1.build_Tree(1,1,m);
T2.build_Tree(1,1,m);
for (int k=1;k<=m;k++){
if (k&1) T1.update(1,k,min(dp[0][i][k],dp[1][i][k])-k-1);
else T2.update(1,k,min(dp[0][i][k],dp[1][i][k])-k-1);
}
for (int j=1;j<=m;j++)
{
if(s[i][j]!='X') continue;
int pos=0,x=min(dp[1][i][j],dp[2][i][j]);
if (x<=ans) continue;
if (j&1) pos=T1.query(1,j,x+j-1,-j);
else pos=T2.query(1,j,x+j-1,-j);
if (pos) ans=max(ans,pos-j+1);
}
}
printf("%d\n",ans);
return 0;
}
the trip on …
数据范围很大，所以考虑使用线段树，考虑每次更新x到n加上y，然后i从x+1到n，每次更新i到n加上d，但是这样的复杂度会超时，因为每次更新的时候会多一个n，前缀和的做法，线段树和树状数组同时用，每次进行操作1的时候，用树状数组将这个点更新为y（用于处理首项和的问题）
，然后用线段树把整个【x+1,n】的值全部加上1（用于判断有多少个d的前缀和），然后操作二的时候，直接用树状数组统计一下x之前所有的和，实际上就是累加了多少个首项，然后用线段树取【1，x】里面的1然后乘以一个d就好了，最后加上a[i]就好，最后a[i]要减去这个值，
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
typedef double db;
const int maxn=1e5+5;
const int mod=1e9+7;
const int INF=1e8+7;
const int inf=1e15+8;
ll a[maxn];
ll c[maxn],n,d;
int lowbit(int x){
return x&(-x);
}
void up(int x,ll d){
while (x<maxn){
c[x]+=d;
c[x]%=mod;
x+=lowbit(x);
}
}
ll getsum(int x){
int ans=0;
while (x){
ans+=c[x];
c[x]%=mod;
x-=lowbit(x);
}
return ans;
}
struct TREE{
ll l,r,val,lazy;
void fun(ll tmp){
lazy+=tmp;
val+=(r-l+1)*tmp;
}
}tre[maxn*4];
void pushdown(int id){
if (tre[id].lazy)
{
tre[id<<1].fun(tre[id].lazy);
tre[id<<1|1].fun(tre[id].lazy);
tre[id].lazy=0;
}
}
void pushup(int id){
tre[id].val=tre[id<<1].val+tre[id<<1|1].val;
}
void build(int id,int l,int r){
tre[id].l=l,tre[id].r=r,tre[id].lazy=0;
if (l==r) tre[id].val=0;
else{
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
pushup(id);
}
}
void update(int id,int st,int ed,int val){
int l=tre[id].l,r=tre[id].r;
if (st<=l&&ed>=r) tre[id].fun(val);
else {
pushdown(id);
int mid=(l+r)>>1;
if (st<=mid) update(id<<1,st,ed,val);
if (ed>mid) update(id<<1|1,st,ed,val);
pushup(id);
}
}
ll query(int id,int st,int ed){
int l=tre[id].l,r=tre[id].r;
if (st<=l&&ed>=r) return tre[id].val;
else {
pushdown(id);
int mid=(l+r)>>1;
ll sum1=0,sum2=0;
if (st<=mid) sum1=query(id<<1,st,ed);
if (ed>mid) sum2=query(id<<1|1,st,ed);
pushup(id);
return sum1+sum2;
}
}
void solve(){
int m;
scanf("%lld%d%lld",&n,&m,&d);
for (int i=1;i<=n;i++)
scanf("%lld",a+i);
memset(c,0,sizeof(c));
build(1,1,n);
ll tot=0;
while (m--){
int op,x,y;
scanf("%d%d",&op,&x);
if(op==1){
scanf("%d",&y);
up(x,y);
update(1,x+1,n,1);
}
else {
ll tmp=getsum(x)+query(1,1,x)*d+a[x];
printf("%lld\n",tmp%mod);
a[x]-=tmp;
}
}
}
int main(){
int t=1;
scanf("%d",&t);
while (t--){
solve();
}
return 0;
}
Momenta公司福利 292人发布
投递腾讯等公司10个岗位 >