k倍区间--线段树60/map+思维100

1.线段树/前缀和都是n方级别的，40%超时

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<int,int> pii;
int n,k,an;
struct tree
{int l,r;ll s,laz;
}tr[10*N];
ll in[10*N];
void bulid(int i,int l,int r)
{tr[i].l=l;tr[i].r=r;tr[i].laz=0;if(l==r){tr[i].s=in[l];return ;}int mid=(l+r)>>1;bulid(2*i,l,mid);bulid(2*i+1,mid+1,r);tr[i].s=tr[2*i].s+tr[i*2+1].s;
}
void pushdown(int i)
{if(tr[i].laz!=0){tr[2*i].laz+=tr[i].laz;tr[2*i+1].laz+=tr[i].laz;int mid=(tr[i].l+tr[i].r)>>1;tr[i*2].s+=tr[i].laz*(mid-tr[2*i].l+1);tr[2*i+1].s+=tr[i].laz*(tr[i*2+1].r-mid);tr[i].laz=0;}return ;} ll search(int i,int l,int r){if(l<=tr[i].l&&tr[i].r<=r){return tr[i].s;}ll sum=0;if(tr[i*2].r>=l) sum+=search(2*i,l,r);if(tr[2*i+1].l<=r) sum+=search(2*i+1,l,r);return sum;}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++)cin>>in[i];bulid(1,1,n);for(int i=1;i<=n;i++) for(int j=i;j<=n;j++){if(search(1,i,j)>=0&&search(1,i,j)%k==0){an++;}}cout<<an;return 0;
}